2022-12-31

RedSpica Winter Selectionを開催しました

こんにちは

　RedSpicaです．12月29日(木)にRedSpica Winter Selectionというコンテストを開催しました．

mojacoder.app

　非常にたくさんの方にご参加いただきました．本当にありがとうございます．せっかくなので感想的なのを書き残しておこうと思います．

1．You Want to Play?
2．Closeness of the Day
3．Count Up Ikkyu
4．Find a RedSpica
5．Partition of N
6．Load to cocoa
7．Knapsack Expect i-th
8．MakeMany Buri-Oden
9．Function Composition
10．その他
11．全体の感想

1．You Want to Play?

　FA 0:59bayashikoさん

　今年の夏休みは本当にずっとValorantをしていました．ずっと目標としていたゴールドに達することもできました．

　問題概要もゲーム内の設定そのままです．題名はChamberというエージェントがアルティメットアビリティを使う際のセリフ「遊びたいのか？相手になろう」の英語版"You want to play? Let's play"からとりました．リンクには今年開催されたVCT2022 Stage1 Masters-ReykjavíkでのTenZ選手の配信の切り抜きが埋め込まれています．SugarZ3ro選手がACEで試合を終わらせるすごいシーンなのでよければ見てください．

2．Closeness of the Day

　FA 5:12 bayashikoさん

　2問目なので簡単なループっぽい問題にしたいものの，なんか特殊な問題にしたかったのでだいぶ前にTwitterで見たものを原案にしました．

2022年の1/19が終わってしまった（ダブル・ミーニング）
— kakiraちゃん☃️ (@kakira9618) 2022年1月19日

　知っていた方はTextで提出してもらっても，知らなかった方は愚直にループを回して計算してもいいです．言語によっては日付を持ってこれるライブラリがあるらしいのでそれを用いてもいいです．

　想定解はそれぞれの月の日数を手打ちで打ってループ回すみたいなのなんですが，それを手打ち(知らない場合は調べてから手打ち)するくらいの面倒くささは許してください．

3．Count Up Ikkyu

　FA 7:23 hourenさん

　ある数学の本を見てたら原案が生えたので解答を見たら結構きれいでびっくりしました．なんかこういうの有志コンで出たらまあまあ嫌なので出さないようにしたいなって思っていたのですが，まあいいかなと思い出しました．よかったら解説の閲覧&いっきゅうのフォロー↓お願いします．

https://twitter.com/ikkyufacku

4．Find a RedSpica

　FA 13:14 roarisさん

　与えられた状況を無向グラフとして見たとき，各連結成分の頂点に書かれた数字のうち1番大きなものが書かれているものが赤である頂点を数える問題です．解法はUFでもグラフの探索アルゴリズムでもなんでも解けます．ただMojaCoder上のジャッジステータスの関係でちょっと困惑した方を数名みかけました．コンテストのトップページに書いておけばよかったですね，配慮不足でした．PythonでDFSを書いた方は再帰の回数の上限を上げているかどうかを確認してみてください．

　オリヴェルっていうのは僕が小学校の頃やっていたネットゲームで飼っていたペットの名前です．特になにかを参考にしたわけではないんですが，中二感があってなんかかっこよくないですか？

　グラフの各頂点を星と見立てて，連結成分を1つの星座とみる．なんかいい感じですよね．問題名もシンプルでなんかかっこいいと思っている結構自信作です．

　リンクにはレヴュースタァライトの星見純那さんの紹介ページが埋め込まれています．「人には定めの星がある，綺羅星　明星　流れ星」というのは彼女の口上で，舞台に登場した際に発するセリフです．

　サンプル2の各星のつながれた関係は実際のおとめ座の関係を参考にしました．星の等級というのは数字が小さいほど明るいので，明るい順に暗い星の等級を振りなおしました．「頂点に立つのはただ1人」というのはこれもレヴュースタァライトの天堂真矢さんのセリフです．「This is 天堂真矢」でおなじみです．

5．Partition of N

　FA 5:48 17さん

　 $1 \leq x \leq N$ に対して，重さが $x$ ，価値が $d(x)$ ，許容容量が $N$ であるナップザック問題を解く問題です．

　自分が考えた問題はいくらでも簡単に見えてしまうのを考慮してなかったのですが「ナップザック問題に落とすの賢い」といった感想を何件か見たので意外とむずかしかったのかなあとこの場所/点数に設定したのが少し反省です(実際5問目と6問目の正解者数が逆転していました)．問題文が読みづらい/サンプルが少ないみたいな感じで誤読を誘っていたら本当に申し訳ないです．

　「 $\{a_i\}$ は互いに異なる」という条件が入っているのは，これがないと $1$ を $N$ 個用意して $N$ を達成して終わってしまうからなんですね．とはいえ01ナップザック問題を解くならあまり関係ないのですが．

　リンクには12 Days Of Christmasという歌が埋め込まれています．この歌は歌詞を見ると「1,2,1,3,2,1,4,3,2,1,...」という感じで数字を数え上げるのですが，それが「互いに異なる数字を合わせる」とか「この問題の計算量が $O(N^2)$ となる」みたいな感じで若干ヒント？でした．あとクリスマスが近かったのもあります．

6．Load to cocoa

　FA 9:38 17さん

　地点 $1$ からのDijkstra法と地点 $N$ からのダイクストラ法で2つの配列をもつのが想定解です．頂点を3倍して1つの配列でやるみたいな解法で解いてる方もいたようです．

　問題準備が終わってから典型90問にほぼ同じ問題が出題されていることに気づいたのですが，せっかく書いたので出題しました．かなり典型テクニックということですね．

atcoder.jp

　この問題のテストケースを作ってる時に思ったんですが，

$N$ 頂点 $0$ 辺のグラフを考える．以下の操作をグラフが連結になるまで続ける．

・ $1 \leq u,v \leq N$ を満たす $u,v$ をランダムに決める．

・もし $u$ と $v$ が連結でないならば $u,v$ 間に辺を張り，そうでないならば何もしない

っていうのって操作回数の期待値ってどれくらいになるんですかね？テストケースを作ってる時の感じでは $N=10^5$ の時でも結構一瞬で生成できて，個人的には「コンプガチャの要領で $N \log N$ 回くらいかな」と思ったのですが証明ができず．何かわかった方がいたらご一報ください．

　リンクには七河みこさんのユニバースの動画が埋め込まれています．彼女は世界各地に旅行をするのが好きで，いろいろな場所に1人で行くそうです．問題とかかってる部分は旅行と移動くらいなんですが，とてもいい動画なのでよければ見てください．

7．Knapsack Expect i-th

　FA 17:49 17さん

　左右からナップザック問題を解いて，それを利用して各 $i$ に対して問題をうまく解けばよいです．添え字をバグらせないように注意が必要です．

　「両端からやる」「ナップザック問題を解く」というのが5問目と6問目で若干かぶるのでどういう問題配置にしようかなと思っていました．しかし感想を見ている感じこれも問題作成者はいくらでも簡単に見える理論からあまり関係なかったようです．

最近は軽装で旅行行くの慣れました
— コンテストでません (@niboshi_wakai) 2022年12月30日

　コンテスト中LayCurseさんがかなりの時間この問題で詰まっていたのでこっちの不備があったのかと思って滝のような汗を流していました．無事に正解していただけてよかったです．

　リンクには北海道大学の石川先生の質問解答PDFが埋め込まれています．2年前に位相空間論の授業を受けているときにネットの海でこのPDFを見つけた覚えがあります．コンパクトの定義のたとえが結構しっかり焼き付いていたので引用させてもらいました．

8．MakeMany Buri-Oden

　FA 3:09 dyktr_06さん

　 $\max \{ \min \{ a_i+a_j, b_i+b_j\} \}, 1 \leq i \leq j \leq N$ を求める問題です．なんと既出らしい．

8番のFAを取りました (3:09)

過去にほぼ同じ問題を作っています……https://t.co/rsEZ8EWCss
— やきとり (@yktr_drm06) 2022年12月29日

　セグ木に載せて二分探索が想定なのですが，他にもいろいろな解法で解けるようです．

　実はコンテストはこの問題を除いた8問100分でやる予定だったのですが，急にこの問題も思いついたので問題数を増やして時間も少し伸ばしました．せっかくburiodenさんから名前をお借りしたのにむずかしめの問題になってしまったのは少し申し訳なかったです．

　富山県は鰤が有名らしいのですが，卒業するまでにおいしいのを食べてから富山を出ていきたいですね．そもそも卒業が怪しいですが．

　リンクに埋め込まれているのは乃木坂46のジコチューで行こう！です．MVも曲もとても良いです．

9．Function Composition

　FA 6:20 LayCurseさん

　剰余を取る値が小さいのでダブリングで前計算ができます．「関数の合成がダブリングの本質ではないか」と考えているところがあり，逆にそれをそのまま出したら面白いんじゃないかと思って出題しました．

　コンテスト中にある参加者の方から「 $f^{(0)}(x)$ は $x$ では？」という趣旨の質問をいただき，追加で説明を書きました．その質問をもらって急いで調べたところ， $f^{(1)}(x)=f(x)$ と記述しているページが1番最初にヒットしたのでリサーチ不足だったかなと反省です．ただ，今回のコンテストであった不備はこれくらいだったのでよかったです．

　この問題も値を計算する際のオーバーフローで不正解となる提出がジャッジステータスが意図したものと違うものが出て困惑した参加者の方もいたようです．「解法は合ってるはずなのにACにならない」という方はオーバーフローしていないか確認してみてください．

　リンクには虹のコンキスタドールのサマーとはキミと私なりっ！！が埋め込まれています．虹のコンキスタドール通称虹コンは夏曲を全面的に押しているグループで，この曲は虹コン7年目に出された夏曲です．”何度も”が6個続いているのはこれまでの6年を表しており，この曲が7年目だよというアピールになっているようです．

10．その他

優勝 41:13 ei1333さん

全問完答者 10名

1st 41:13 ei1333さん

2nd 46:50 + 5:00 LayCurseさん

3rd 57:03 + 5:00 bayashikoさん

4th 73:57 +15:00 akuaさん

5th 80:10 + 10:00 ecotteaさん

6th 87:15 + 10:00 roarisさん

7th 99:51 + 15:00 Daylightさん

8th 99:21 + 25:00 siganaiさん

9th 114:51 + 15:00 dyktr_06さん

10th 111:14 +25:00 mikamさん

各問題正解者/提出者

1．You Want to Play? 58/59

2．Closeness of the Day 58/58

3．Count Up Ikkyu 49/50

4．Find a RedSpica 53/54

5．Partition of N 33/33

6．Load to cocoa 40/40

7．Knapsack Expect i-th 23/20

8．Make Many Buri-Oden 18/22

9．Function Composition 14/17

11．全体の感想

　改めて本当に多くの方にご参加いただきありがとうございました．夏に開催した際は30名弱の方に参加していただいたので今回もそれくらい参加してもらえるといいなと思っていたところ予想を大幅に上回る参加者でとてもうれしく思います．また，特に不備もなくコンテストを終了することができてよかったです．

　終了後の感想は(観測できる範囲で)すべて見させていただきました．「楽しかった」というものをはじめとしたさまざまな感想を寄せていただきありがとうございます．励みになります．

　開催中/開催後に思ったのですが，やはりこのセットで120分は少し短かったですね．「自分が作った問題は簡単に見えてしまう」+「ためていた原案はすべて吐きたい」+「有志コンで時間が長いと集中力が切れる/のちの感想共有の時間が深夜になってしまう」→「このセットをこの時間で行こう」というのが理由です．それでも上位勢はしっかり時間内に全問完答していてさすがだなと思いました．

　個人的にはAtCoder水色くらいで戦える典型的な問題/よく考えればわかる問題をそろえたつもりです．解説も書いたのでよければ解けなかった問題もあきらめずに挑戦してみてください．

　コンテストを開催するにあたり全体テスターを引き受けてくださったzeronosu77108さん

　問題文のおはなしに登場してくれた競プロ仲間のみんな

　素晴らしいコンテストサイトを提供してくださったマクタモトさん

　そして最後になりますが，コンテストに参加してくださった参加者の皆さん，この度は本当にありがとうございました．

　またコンテストを開催する機会があったときはぜひご参加ください．

RedSpica

2021-12-03

ABC202 D - aab aba baa 別解

ABC202 D - aab aba baaの桁DP+二分探索を用いた解法の解説です．

問題リンク

提出コード

問題概要

$A$ 個のaと $B$ 個のbからなる長さ $A+B$ の文字列のうち，辞書順で $K$ 番目のものを求めてください．

制約

・ $1 \leq A,B \leq 30$

・ $A$ 個のaと $B$ 個のbからなる長さ $A+B$ の文字列が少なくとも $K$ 個は存在することが保証される

解法

aを $0$ ，bを $1$ に直します．すると，aとbからなる文字列は2進数とみなすことができます．

この操作をしたあと，元の問題は「 $1$ が $B$ 回使われている2進数の小さいほうから $K$ 番目の数は何か」と言い換えることができます．

$A+B$ 桁に満たないものは $A+B$ 桁になるまで先頭に $0$ をつけ足せば $0$ が $A$ 個という条件を満たします．また，同じ桁数同士の整数の大小関係はそれを文字列として見たときの辞書順の大小関係と一致します．よって，上の言い換えが成立することがわかります．

次に以下の小問題 $f(x)$ を考えます．

・ $f(x):=$ 2進法表記された整数 $x$ 以下に $1$ が $B$ 回使われている数は $K$ 個未満かどうか

$f(0)=True$ であって，十分大きな整数 $c$ に対しては $f(c)=False$ です．また， $x'$ が $f(x')=True$ となるならば $0 \leq y \leq x'$ を満たす任意の $y$ に対して $f(y)=True$ です．同様に， $x'$ が $f(x')=False$ となるならば $x' \leq y$ を満たす任意の $y$ に対して $f(y)=False$ です．よってこの小問題には単調性があり，ある $m$ が存在して $f(m)=True,f(m+1)=False$ となります．この時の $m+1$ が答えとなります．

小問題の判定について考えてみましょう．「〇〇以下の条件を満たすものの個数」という問題は桁DPというアルゴリズムを用いて求めることができる場合が多く，今回もそれを用いて判定することを考えます．

配列の定義

$dp[i][j][?]:=$ 上から $i$ 桁目まで見て， $1$ の個数が $j$ 個で， $x$ より小さいことが確定しているかどうか( $?$ が $0$ なら $x$ ちょうど， $1$ なら $x$ より小さいことが確定)

遷移

・ $?=1$ からは $?=1$ にのみ遷移

・ $?=0$ から $?=1$ に遷移

・ $?=0$ から $?=0$ に遷移

それぞれの遷移ごとに $j$ の値を増やしたりそのままにしたりして遷移します(詳しくは僕の提出を参考にしてください)．

判定内容

$x$ を2進数表記して，その桁数を $n$ とすると， $dp[n][B][0]+dp[n][B][1] \lt K$ かどうか

以上の方法を用いて小問題を構成します．

先に述べたようにこの小問題には単調性があるので，二分探索を用いて答えとなる整数を求めることができます．最後に求めた答えを2進数に変換し， $0$ をaに， $1$ をbに変更した文字列が最終的な答えとなります．

小問題を $1$ 回解くごとに， $x$ の桁数を $n$ とすると $O(n ^ 2)$ であり，二分探索の探索範囲を $l,r$ とすると小問題を $\mathbf{log}(r-l)$ 回程度行うので，全体としての計算量は $O(n ^ 2 \mathbf{log}(r-l))$ となり，この問題の条件下では十分高速です．

提出コード

Bonus問題

aが $A$ 個，bが $B$ 個からなる文字列 $S$ が与えられます．aが $A$ 個，bが $B$ 個からなる文字列すべてのうち $S$ は辞書順で何番目か． $10 ^ 9 +7$ で割ったあまりを求めよ．(要するに元の問題の逆操作です)

・ $1 \leq A,B \leq 10 ^ 3$

2021-10-04

おもしろかったAtCoderの問題たち

こんにちは

　RedSpicaです．今まで解いてきたAtCoderの問題のうち「おもしろいな」と思ったものを紹介します．知らない間に追加されたり消されたりします．

　点数とかDifficultyとか出題日時は解く前に見て欲しくないので載せていません．問題概要を見て解けそうだったらチャレンジしてもらって，無理そうだったら諦めてください．難易度順に並んでいるとは限りません．

問題一覧

・一問目

・LEQ

・Anything Goes to Zero

・Product of Arithmetic Progression

・Balanced Neighbors

・01 Matrix

・GCD Sequence

・MAD TEAM

・Equal Weight

・Built?

・Keep Graph Connected

・Packing Potatoes

一問目

問題リンク

問題概要

文字列 $S$ の頭文字を出力してください．

制約

・ $1 \leq |S| \leq 100$

・ $S$ は半角英数字からなる文字列

LEQ

問題リンク

問題概要

長さ $N$ の整数列 $A=(A_1,A_2,...,A_N)$ が与えられます． $A$ の連続するとは限らない，長さが $2$ 以上である部分列 $A'=(A'_1,A'_2,...A'_k)$ のうち以下の条件を満たすものの個数を求め， $998244353$ で割ったあまりを求めてください．

条件： $A'_1 \leq A'_k$

制約

・ $2 \leq N \leq 3 \times 10 ^ 5$

・ $1 \leq A_i \leq 10 ^ 9$

Coprime Present

問題リンク

問題概要

$A$ 以上 $B$ 以下の整数が書かれたカードをそれぞれ $1$ 枚ずつ，計 $B - A +1$ 枚持っています．以下の条件を満たすようなカードの選び方(選ぶ枚数は $0$ 枚でもよい)は何通りありますか．

条件：選ばれたカードのどの相異なる $2$ 枚に書かれた数も互いに素である．

制約

・ $1 \leq A \leq B \leq 10 ^ {18}$

・ $B - A \leq 72$

GCD on Blackboard

問題リンク

問題概要

$N$ 個の整数 $A_1,A_2,...A_N$ のうち $1$ つ選んで好きな正整数に書き換えます．書き換えた後の $N$ 個の整数の最大公約数の最大値を求めてください．

制約

・ $2 \leq N \leq 10 ^ 5$

・ $1 \leq A_i \leq 10 ^ 9$

2017-like Number

問題リンク

問題概要

以下の条件を満たす奇数を2017に似た数とします．

条件： $N$ も $(N+1) \div 2$ も素数である

ここで以下の問に $Q$ 回答えてください．問 $i$ の形式は以下の通りです．

問 $i$ ： $l_i,r_i$ が与えられるので， $l_i$ 以上 $r_i$ 以下の2017に似た数の個数を求めてください

制約

・ $1 \leq Q \leq 10 ^ 5$

・ $1 \leq l_i \leq r_i \leq 10 ^ 5$

joisino's travel

問題リンク

問題概要

$N$ 頂点 $M$ 辺の無向グラフが与えられます．辺 $i$ は頂点 $A_i$ と頂点 $B_i$ を結んでいて，その距離は $C_i$ です．あなたは頂点 $r_1,r_2,...r_R$ を訪れることになりました．訪れる頂点の順番を適切に選んだときその移動距離の最小値はどうなるでしょうか．

制約

・ $2 \leq N \leq 200$

・ $1 \leq M \leq N \times (N-1) /2$

・ $1 \leq C_i \leq 10 ^ 5$

Easy

・ $2 \leq R \leq \mathbf{min}(8,N)$

Hard

・ $2 \leq R \leq \mathbf{min}(13,N)$

・与えられるグラフは多重辺や自己ループを持たず，どの頂点間も辺を経由して移動することができる

Anything Goes to Zero

問題リンク

問題概要

$\mathbf{popcount}(n)$ を $n$ を $2$ 進数表記したときの1の個数とします．たとえば $\mathbf{popcount}(3)=2$ ， $\mathbf{popcount}(0)=0$ です．

$f(n)$ を「 $n$ を $\mathbf{popcount}(n)$ で割ったあまりに置き換える」という操作を繰り返した際に $n$ が $0$ になるまでの操作回数とします．

以下は $n=7$ の例で， $2$ 回の操作で $n$ が $0$ になります．

・ $\mathbf{popcount}(7)=3$ なので $7$ を $3$ で割ったあまりである $1$ に置き換える．

・ $\mathbf{popcount}(1)=1$ なので $1$ を $1$ で割ったあまりである $0$ に置き換える．

$2$ 進数表記で $N$ 桁の整数 $X$ が与えられます． $1 \leq i \leq N$ を満たす整数 $i$ について， $X$ の上から $i$ 桁目のビットを反転した整数を $X_i$ とします． $f(X_1),f(X_2),...,f(X_N)$ をそれぞれ求めてください．

制約

・ $1 \leq N \leq 2 \times 10 ^ 5$

・ $X$ は $2$ 進数表記で $N$ 桁の(先頭が $1$ とは限らない)整数

Product of Arithmetic Progression

問題リンク

問題概要

以下の問に $Q$ 回答えてください．問 $i$ の形式は以下の通りです．

問 $i$ ：初項 $x_i$ ，公差 $d_i$ ，項数 $n_i$ の等差数列の総積，つまり

$\displaystyle \prod_{k=1}^{n_i} (x_i+d_i (k-1))$

を $10 ^ 6 +3$ で割ったあまりを求めてください．

制約

・ $1 \leq Q \leq 10 ^5$

・ $0 \leq x_i ,d_i \leq 10^ 6 + 2$

・ $1 \leq n_i \leq 10 ^ 9$

Balanced Neighbors

問題リンク

問題概要

頂点に $1$ から $N$ の番号がついた $N$ 頂点の単純かつ連結である無向グラフであって，以下の条件を満たすものを $1$ つ構成してください．

条件：ある整数 $S$ が存在して，任意の頂点についてその頂点に隣接する頂点の番号の値の和は $S$ となる

条件を満たすグラフが必ず存在することが証明できます．

制約

・ $3 \leq N \leq 100$

01 Matrix

問題リンク

問題概要

$H$ 行 $W$ 列からなるマス目を $0$ か $1$ で埋めることを考えます．以下の条件を満たす埋め方を $1$ つ示してください．不可能な場合はそれを報告してください．

条件

・どの行についてもその行に含まれる $0$ の個数と $1$ の個数のうち小さいほうが $A$ である．

・どの行についてもその列に含まれる $0$ の個数と $1$ の個数のうち小さいほうが $B$ である．

制約

・ $1 \leq H,W \leq 1000$

・ $0 \leq A,B$

・ $2 \times A \leq W$

・ $2 \times B \leq H$

GCD Sequence

問題リンク

問題概要

正整数の集合 $S = \left\{ a_1, a_2, ... a_N \right\}$ が以下の条件を満たす場合特別な集合であると言われます．

条件：どの $1 \leq i \leq N$ についても $a_i$ と $S$ のその他の要素の和の最大公約数は $1$ ではない．

要素数 $N$ の特別な集合であって， $\mathbf{gcd}(a_1, a_2, ... a_N) =1$ であり， $\mathbf{max}(a_1, a_2, ... a_N) \leq 30000$ であるものを $1$ つ求めてください．この問題の制約下では条件を満たすものが少なくとも1つは存在することが保証されます．

制約

・ $3 \leq N \leq 20000$

MAD TEAM

問題リンク

問題概要

$N$ 人のメンバーがいて，それぞれのメンバーは $5$ つのステータスがあります． $i$ 人目の $j$ 個目のステータスの値は $S_{i,j}$ です．便宜上 $i$ 人目のメンバーの番号を $i$ とします．

$N$ 人の中から $3$ 人を選んでチームを組みます． $3$ 人のメンバーの番号が $x_1,x_2,x_3$ であったとき，そのチームの総合力は以下で計算されます．

チームの総合力 $= {\underset{1 \leq j \leq 5}{\mathbf{min}}} \left ( {\underset{1 \leq i \leq 3}{\mathbf{max}}(S_{{x_i},j})} \right)$

このとき，チームの総合力としてあり得る最大の値を求めてください．

制約

・ $3 \leq N \leq 3000$

・ $1 \leq S_{i,j} \leq 10 ^ 9$

Equal Weight

問題リンク

問題概要

$0$ から $N-1$ までの番号がついた $N$ 個のシャリと， $0$ から $M-1$ までの番号がついた $M$ 個のネタがあります．シャリ $i$ の重さは $A_i$ で，ネタ $j$ の重さは $B_j$ です．

あなたは寿司の握りを $2$ つ作りたいです． $1$ つの握りはちょうど $1$ つのシャリとネタを組み合わせ作ることで作られます．

あなたは $2$ つの握りの重さが等しくなるようにしたいです．これが可能かどうか判定し，可能ならばその作り方を $1$ つ示してください．なお，同じシャリやネタを $2$ 回使うことはできません．

制約

・ $2 \leq N,M \leq 2 \times 10 ^ 5$

・ $1 \leq A_i \leq 10 ^ 6$

・ $A_i \neq A_j (i \neq j)$

・ $1 \leq B_i \leq 10 ^6$

・ $B_i \neq B_j (i \neq j)$

Built?

問題リンク

問題概要

平面上に $N$ 個の街があり， $i$ 個目の街は座標 $(x_i,y_i)$ にあります．同じ座標に複数の街がある場合もあります．座標 $(a,b)$ にある街と座標 $(c,d)$ にある街の間に道を造るのには $\mathbf{min}(|a-c|,|b-d|)$ 円かかります．街と街の間以外に道を造ることはできません．

任意の $2$ つの街の間を，道を何本か通って行き来できるようにするためには最低で何円必要でしょうか．

制約

・ $2 \leq N \leq 10 ^ 5$

・ $0 \leq x_i,y_i \leq 10 ^ 9$

Keep Graph Connected

問題リンク

問題概要

$1$ から $N$ の番号が付いた $N$ 個の頂点と $1$ から $M$ の番号が付いた $M$ 本の辺からなる連結な無向グラフが与えられます．このグラフには多重辺が存在するかもしれませんが，自己ループはありません．

このグラフのそれぞれの辺には $1$ 以上 $N$ 以下の整数で表されるラベルがついています．辺 $i$ にはラベル $c_i$ がついており，頂点 $u_i,v_i$ を双方向につなぐ辺です．

あなたはそれぞれの頂点に $1$ 以上 $N$ 以下の整数を書き込んだのち(頂点に書き込まれた整数に重複があっても構いません)，以下の条件を満たす辺のみを残してそれ以外の辺を取り除くことにしました．

条件：辺の両端の頂点に書き込まれた整数を $x,y$ として， $x,y$ のいずれか一方のみが辺についたラベルと等しい

上記の条件を満たさない辺を取り除いたあとのグラフも連結のままであるような頂点への整数の書き込み方が存在するかどうか調べ，存在するならその一例を，存在しないならば存在しないことを報告してください．

制約

・ $2 \leq N \leq 10 ^ 5$

・ $N-1 \leq M \leq 2 \times 10 ^ 5$

・ $1 \leq u_i,v_i,c_i \leq N$

・与えられるグラフは連結

・与えられるグラフに自己ループはない

Packing Potatoes

問題リンク

問題概要

ベルトコンベアに載って $10^{100}$ 個のじゃがいもが $1$ 個ずつ流れてきます．流れてくるじゃがいもの重さは長さ $N$ の数列 $W=(W_0,W_1,...,W_{N-1})$ で表され， $i (1 \leq i \leq 10 ^ {100})$ 番目に流れてくるじゃがいもの重さは $W_{(i-1) \mathbf{mod} N}$ です．ここで， $(i-1) \mathbf{mod} N$ は $i-1$ を $N$ で割ったあまりを表します．

あなたはまず空の箱を用意し，次のルールに従ってじゃがいもを順番に箱に詰めていきます．

・じゃがいもを箱に入れる．箱に入ってるじゃがいもの重さの総和が $X$ 以上になったらその箱には蓋をし，新たに空の箱を用意する．

$Q$ 個のクエリが与えられます． $t(1 \leq t \leq Q)$ 番目のクエリでは，正整数 $K_t$ が与えられるので， $K_t$ 番目に蓋をされた箱に入っているじゃがいもの個数を求めてください．問題の制約下で，蓋をされた箱が $K_t$ 個以上存在することが証明できます．

制約

・ $1 \leq N,Q \leq 2 \times 10^{5}$

・ $1 \leq X \leq 10^{9}$

・ $1 \leq W_i \leq 10^{9}$

・ $1 \leq K_t \leq 10^{12}$

2020-12-31

留年宣告を受けました

こんにちは

　「留年した」という文章ってどの時系列を指しているかよくわからないですよね．単位が認定されずその学年をもう1度繰り返すことが確定した瞬間なのか，その繰り返した学年が終わったときのことなのか．

　その点では「留年しそう」という文章は時系列がわかりやすく，確実に「その学年をもう1度繰り返す前」のことを指していることがわかります．

　僕の今の状態は少なくとも「留年しそう」ではなくなりました．悪い意味で...

　「単位が認定されずその学年をもう1度繰り返すことが確定した」ので，なんでこうなっちゃったかなーと反省しながらこれまでの大学生活を振り返ります．

1年生前期
1年生後期
2年前期
2年後期
3年前期
その後
最後に

1年生前期

　授業開始日を間違えて，初日の授業を知らぬ間に切ります．は？この時点で今後の大学生活がかなり不安になりました．

　そして，友達ができません．新入生の知り合いを作ろう会みたいなものにことごとく出ていなく，自分から他人に話しかける勇気もありません．「まあひとりでもなんとかなるでしょ」と思っていたのですが，大学生活で友達がいないというのは余程強い人間でもない限り詰みます．このことを詰んでから知りました．履修登録のこと，授業開始までのイベントのこと，授業開始日のことはすべて自分で把握しておく必要があります．

　幸いにも学科の授業が始まった時に出会いがあります．前の席に座っていた学生が，僕の書いたアンケートの名前をみて「ツイッターのアカウントこれでしょ」と告げてきます．彼と仲良くなり，彼伝いでいろいろな人間と出会います．

　人との出会いに，感謝＿＿＿＿＿＿

　それから割と生活は順調だったのですが，GWが明けたあたりからいろいろと考え込んでしまい学校に行かなくなります．たぶん五月病というやつです．1か月半くらいの間あまり学校に行かない日々が続きます．7月の頭くらいからまた学校に行き始めるのですが，時すでに遅しといった感じで単位が死にます．明らかに出席日数が足りてないのとか，明らかにテストの出来が悪いのに単位が出た授業もあって「なんだこれ」となっていましたが，最初の1か月まじめにやっていた貯金だと思ってありがたく受け取りました．

1年生後期

　1番順調だったと思います．1年前期で何も学べなかった解析学を教科書読み込んで前期に授業でやったところまでは理解して，後期の解析学にもついていけておもしろかったなーと思いました．

　僕が所属する学部では「英語コミュニケーション(英会話の授業)」と「英語リテラシー(座学の授業)」の2種類を1年の前後期併せて4つとらないといけません．しかし，TOEICで規定の点数以上を取るとそのうちの何個かを単位認定という形で消すことができます．

　僕は偶然にも前期に受けたTOEIC IPテストで規定以上の点数を取っていたので，後期の英語コミュニケーションを消すことにした(コミュ障なのでできるだけ会話型の授業は避けたいから)のですが，英語リテラシー初回の授業で「この授業の目標は英語を理解することではなく楽しく話せるようになることです」みたいなスライドを見せられて「？？？？？？？？？」となり，僕が単位認定によって出なくてよかった英語コミュニケーションの授業はガッツリ座学という話を友達に聞き「？？？？？？？？？？」となりました．結局英語リテラシーは15回中2回くらいしか行かず単位を落としました．

2年前期

　2年生が始まりました．2年生が始まる前にアルバイトとAtCoderを始めました．競技プログラミングを始めたことにより，起きてる時間は常に競技プログラミングの問題の考察をすることになります．これがかなり最悪で，これのせいで学業と生活習慣が破滅します．

　決して勘違いしてほしくないのは「悪いのはすべて僕で，競技プログラミングは節度を守ってやればとても面白いコンテンツ」ということです．

　競技プログラミングをやってたおかげで，数学科で開講されたプログラミングの授業で大学生活初の秀という成績がでました，やったね！

2年後期

　再履修の英語はリテラシーでもコミュニケーションでもいいというガバガバルールなので，2年後期で英語リテラシーを履修しようとするのですが，履修登録をしようとしたら英語の登録期間がすでに終わっているという罠．なんでミスったかというと，周りの友達は1年生の時に1発で取っている，ないしは2年前期までに取り終わっているという状況だったので英語を取り残しているのは僕だけだったんですね．

　相変わらず競技プログラミングに熱中し，生活が壊れています．半分も出席していないような授業でもとりあえずテストを受けに行ってなぜか成功しちゃうみたいなのが3つくらいあったきがします．

3年前期

　カリキュラム上必修の授業は2年生までで，必修・選択のそれぞれの単位を3年後期までに揃えないと留年が決まります．つまり，2年前期に取るべき授業の再履修を3年前期で落とすと(少なくとも)その時点で確定です．

　結果から言うと，再履修で負けます．

　2年後期にもプログラミングの授業があったのですが，皆欠席・テストの出来もビミョウというフルコンボを決めたのにもかかわらず良という評価が出ました．その先生が持った線形代数の授業が再履修のうちの1つだったので完全に甘く見て，それを落として3年前期で留年が決まりました．

　逆に，他の「これが落ちて留年になるかもしれない」と思った科目は普通に通っていて，しっかり勉強したと思っていた(留年になるかどうかは直接関係ない)科目が落ちてそれも少しショックでした．

その後

　留年が決まる瞬間ってマジでこんな感じなんです．

youtu.be

　「まあさすがに単位出てるんじゃない？」みたいな気でいたら落ちていて，頭が真っ白になった覚えがあります．

　成績が出てから1週間くらい留年したことを引きずっていたんですが，時間が経つにつれあんまり気にしなくなりました．母親から「どこかにいってしまったんじゃないか」と本気で心配されたんですが，さすがにそこまで思い込んだりはしませんでした．

　柄にもなく7月末に3日間のインターンに参加したんですが，その会社から「めちゃくちゃよかったよ，ぜひうちの会社受けて」みたいなメッセージや「10月から22卒の面接あるから受けない？」ってメッセージがPaiza経由で3件くらい来ました．留年確定した次の日には「10月〇〇日に面接やるよ，当然応募するっしょ？」みたいなメッセージがきたのですが，「留年したので来年普通の枠で応募します」という旨のメッセージを送りました．一生懸命就活をしている友人曰く，これはどうやら内々定というやつらしく，大きな獲物を逃したなーといった感じです．

　3年後期が始まってすぐに助言教員と面談があって(これは留年が決まったからとかではなく定期的にあるもの)，その数日後に「線形代数の救済措置がとられるかもしれません」というメールが来たのですが，「企業からの誘いを蹴ってしまったのでそのまま留年します」という返信をしました．

　別に数学が嫌いというわけでは断じてないのですが，正直学びたいものと今学んでいることが少し離れているなと思っていたので大学を辞める考えがないわけでもなかったのですが，「大卒と高卒じゃ給料にだいぶ差が出る」みたいな話を聞いたり，数学科の卒業研究で計算機のゼミが去年からできたりしてそれに参加したいと思ったので学校をやめるのはやめました．

最後に

　数学科には「線形代数とε-δ論法は最低限できるようになったほうがいい」みたいな言い伝えがあります．これは本当にその通りで，線形代数の授業についていけないのはもちろんのこと，様々な分野で急に行列が顔を出してきて先生方も「当然これは知ってるよね？」みたいな感じで授業を進めるので線形代数でつまずくと死にます．本当に線形代数はしっかりやったほうがいい！！！！！！

　それから，当たり前ですが留年はしないほうがいいです．僕のように天から降ってきた内々定をドブに捨ててしまうことになる人はもう見たくないです．

　そして，学業以外の何かに打ち込むときには休学という手もありだったのではないかと思っています．国立大学の場合には無料で休学ができるらしい(僕はしたことがないのでわかりません)ので，研究や開発だけでなく，そういう制度がある以上「ゲームを本気でやるために休学する」みたいな理由があってもいいんじゃないかなと思っています．

ここまで読んでいただきありがとうございました

この記事を読んで留年する人がひとりでも減りますように

RedSpica

2020-12-19

ゴッドフィールドって知ってる？笑

こんにちは

オススメのゲームの話をする Advent Calendar 2020 - Adventarの19日目の記事を担当します．次の日担当のにぼしの記事はコチラ(書いてくれてありがとう)．去年はポケモンの記事を書いたのでよければそちらもご覧ください．

　今年もいろいろなゲームをやりました．パソコンではFall Guys，Valorant，CS:GO，Rocket League，Ultimate Chicken Horseをやり，現実世界(?)ではコヨーテというボードゲームやCHUNITHMという音ゲーをやったりもしました．

　そんな中でも今回紹介するゲームはGod Fieldというゲームです．

godfield.net

　ゲームの内容を端的に説明すると，様々なカードゲームの面白い要素を集めてきたものみたいな感じです．

　もう少し詳しく説明します．

　ゲームは個人戦，チーム戦の2つがありますが，基本的なルールは変わりません．ゲームの開始時にそれぞれのプレイヤーはHPが40，MPが10，お金が20円配られます．MPやお金やカードを駆使して，相手を攻撃し，HPが0になったら(基本的には)負けです．

　説明が下手なのとぜひとも皆さんにやってもらいたいので「とりあえずやってみて」のスタンスで書いているんですが，これだけは知っておいたほうがいいみたいなのを書いておきます．

”はね返す” と ”弾く” の違い
災い
属性
お金・MP

”はね返す” と ”弾く” の違い

　すごく似ているフレーズですが，少し意味が違ってきます．”跳ね返す”は攻撃してきた相手にそのまま返すことを指します．”弾く”は攻撃をランダムで1名にそのまま返すことを指します．つまり，”弾く”は自分に攻撃がそのまま通ることもあれば，全然関係ない第三者を巻き込むこともあります．”跳ね返す”は”弾く”の上位互換だと思っていればいいかもしれません．

　”はね返す”という能力を持った武器があるのですが，そのカードをそのまま使うのは基本的におススメできません．

災い

　ポケモンでいうところの特殊状態です．災いを持っていると場の進行がかなり不利になります．回復できるアイテムをどこで使うか(使った直後に「もうアイテムがない」と読まれて別の災いをつけられる作戦をとられることもあるので)もとても重要です．

　いのちのたまのように「わざと不利な状況になるが，大幅な利益を得ることもできる」というカードもあります．回復アイテムを持っているならそのようなカードも有効的と言えます．

属性

　基本的にはほとんどの武器が無属性の攻撃なんですが，属性がついた攻撃方法もカードによっては存在します．属性攻撃は(闇属性以外は)限られた属性の防具でないと攻撃を防ぐことができないため，「ここでHPを削っておきたい」というときにはとても刺さります．注意してほしいのが，「異なる属性の武器を一緒に使うと(基本的に)無属性になる」という点です．

　そして，1番気をつけなければならない属性は闇属性です．闇属性の攻撃はどんな防具でも守ることができるのですが，攻撃を守り切れなかった場合即死となります．つまり，相手が闇属性のカードを持っているときに防具がないことを知られてしまうと実質負けです．

お金・MP

　カードの中には「自分のアイテムを相手に売りつける」というカードが存在します．売りつけられたものは絶対に買わなければいけないのですが，お金がない時に売りつけられると1MP=1円換算でMPから削られていきます．MPもない時は1HP=1円換算でHPから削られていきます．つまり，お金もMPもない時に高額なものを売りつけることで回避不可能なダイレクトアタックを相手にすることができるので，この手でトドメを指すことも作戦のひとつです．

　また，両替というカードも存在していて，「(HP+MP+お金)の値を保存したまま好きに数値を変えることができる」というものもあります．お金を貯めて一気にHPやMPに両替して場を動かすという戦略を取るときに使えます．

さいごに

　どうですか？やりたくなってきませんか？そんなあなたに朗報です！なんと超超超最近スマートフォン向けのGod Fieldのアプリがリリースされたのです！！！

#ゴッドフィールド

 App StoreとGoogle Playでアプリ配信中です。

iOS https://t.co/uxWYUxNepD

Android https://t.co/VGzSTMmipT pic.twitter.com/aDn4s5ELQn
— グウジ (@guuji) 2020年10月30日

　そして新機能として勝負の結果に応じてレートがつく真剣タイマンモードも追加されています！

古よりインターネットに伝わるゲーム†God Field†を一緒にはじめてみませんか...?

RedSpica

2020-10-13

ABCのAをPythonで，1行で書く

　タイトル通りです．

　自分のためのアーカイブみたいな感じで，新しいものを書き次第追加していきます．

ルール

・できるだけ他人の提出を見ないようにする

・できるだけ短く書く

・セミコロンは使わない

・全部埋めるのを目指す！

　→全部埋まった！(2020/10/25)

　アドバイスがあったら随時教えてください．

220~226
210~219
200~209
190~199
180~189
170~179
160~169
150~159
140~149
130~139
120~129
110~119
100~109
090~099
080~089
070~079
060~069
050~059
040~049
030~039
020~029
010~019
001~009

220~226

ABC226 Round decimals

atcoder.jp

ABC225 Distinct Strings

ABC224 Tires

ABC223 Exact Price

ABC222 Four Digits

ABC221Seismic magnitude scales

atcoder.jp

ABC220 Find Multiple

210~219

ABC219 AtCoder Quiz 2

ABC218 Weather Forecast

ABC217 Lexicographic Order

atcoder.jp

ABC216 Signed Difficulty

atcoder.jp

ABC215 Your First Judge

atcoder.jp

ABC214 New Generation ABC

atcoder.jp

ABC213 Bitwise Exclusive Or

atcoder.jp

ABC212 Alloy

atcoder.jp

ABC211 Blood Pressure

atcoder.jp

ABC210 Cabbages

atcoder.jp

200~209

ABC209 Counting

ABC208 Rolling Dice

ABC207 Repression

ABC206 Maxi-Buying

ABC205 kcal

ABC204 Rock-paper-scissors

atcoder.jp

ABC203 Chinchirorin

atcoder.jp

ABC202 Three Dice

atcoder.jp

ABC201 Tiny Arithmetic Sequence

atcoder.jp

ABC200 Century

atcoder.jp

190~199

ABC199 Square Inequality

atcoder.jp

ABC198 Div

atcoder.jp

ABC197 Rotate

atcoder.jp

ABC196 Difference Max

atcoder.jp

ABC195 Health M Death

ABC194 I Scream

ABC193 Discount

ABC192 Star

ABC191 Vanishing Pitch

atcoder.jp

ABC190 Very Very Primitive Game

atcoder.jp

180~189

ABC189 Slot

atcoder.jp

ABC188 Three-Point Shot

atcoder.jp

ABC187 Large Digits

atcoder.jp

ABC186 Brick

atcoder.jp

ABC185 ABC Preparation

ABC184 Determinant

ABC183 ReLU

ABC182 twiblr

ABC181 Heavy Rotation

atcoder.jp

ABC180 box

atcoder.jp

170~179

ABC179 Pular Form

ABC178 Not

ABC177 Don't be late

ABC176 Takoyaki

ABC175 Rainy Season

ABC174 Air Contitioner

ABC173 Payment

ABC172 Calc

ABC171 αlphabet

ABC170 Five Variables

atcoder.jp

160~169

ABC169 Multiplication 1

ABC168 ∴ (Therefore)

ABC167 Registration

ABC166 A?C

ABC165 We Love Golf

ABC164 Sheep and Wolves

ABC163 Circle Pond

ABC162 Lucky 7

ABC161 ABC Swap

ABC160 Coffee

150~159

ABC159 The Number of Even Pairs

atcoder.jp

ABC158 Station and Bus

atcoder.jp

ABC157 Duplex Printing

atcoder.jp

ABC156 Beginner

atcoder.jp

ABC155 Poor

atcoder.jp

ABC154 Remaining Balls

atcoder.jp

ABC153 Serval vs Monster

ABC152 AC or WA

ABC151 Next Alphabet

ABC150 500 Yen Coins

140~149

ABC149 Strings

atcoder.jp

ABC148 Round One

atcoder.jp

ABC147 Blackjack

atcoder.jp

ABC146 Can't Wait for Holiday

ABC145 Circle

ABC144 9x9

ABC143 Curtain

ABC142 Odd of Oddness

atcoder.jp

ABC141 Weather Prediction

atcoder.jp

ABC140 Password

atcoder.jp

130~139

ABC139 Tenki

ABC138 Red or Not

ABC137 +-x

ABC136 Transfer

ABC135 Harmony

ABC134 Dodecagon

ABC133 T or T

ABC132 Fifty-Fifty

ABC131 Security

ABC130 Rounding

120~129

ABC129 Airplane

atcoder.jp

ABC128 Apple Pie

atcoder.jp

ABC127 Ferris Wheel

atcoder.jp

ABC126 Changing a Character

atcoder.jp

ABC125 Biscuit Generator

ABC124 Buttons

ABC123 Five Antennas

ABC122 Double Helix

ABC121 White Cells

ABC120 Favorite Sound

atcoder.jp

110~119

ABC119 TBD

atcoder.jp

ABC118 B +/- A

atcoder.jp

ABC117 Entrance Examination

atcoder.jp

ABC116 Right Triangle

atcoder.jp

ABC115 Christmas Eve Eve Eve

atcoder.jp

ABC114 753

atcoder.jp

ABC113 Discount Fare

atcoder.jp

ABC112 Programing Education

atcoder.jp

ABC111 AtCoder Beginner Contest 999

atcoder.jp

ABC110 Maximize the Formula

atcoder.jp

100~109

ABC109 ABC333

ABC108 Pair

ABC107 Train

ABC106 Garden

ABC105 AtCoder Crackers

atcoder.jp

ABC104 Rated for Me

atcoder.jp

ABC103 Task Scheduling Problem

atcoder.jp

ABC102 Multiple of 2 and N

atcoder.jp

ABC101 Eating Symbols Easy

atcoder.jp

ABC100 Happy Birthday!

atcoder.jp

090~099

ABC099 ABC

atcoder.jp

ABC098 Add Sub Mul

atcoder.jp

ABC097 Colorful Transceivers

atcoder.jp

ABC096 Day of Takahashi

atcoder.jp

ABC095 Something on It

atcoder.jp

ABC094 Cats and Dogs

atcoder.jp

ABC093 abc of ABC

atcoder.jp

ABC092 Traveling Budget

atcoder.jp

ABC091 Two Coins

atcoder.jp

ABC090 Diagonal String

atcoder.jp

080~089

ABC089 Grouping 2

atcoder.jp

ABC088 Infinite Coins

ABC087 Buying Sweets

ABC086 Product

ABC085 Already 2018

ABC084 New Year

ABC083 Libra

ABC082 Round Up the Mean

atcoder.jp

ABC081 Placing Marbles

atcoder.jp

ABC080 Parking

atcoder.jp

070~079

ABC079 Good Integer

ABC078 HEX

ABC077 Rotation

ABC076 Rating Goal

ABC075 One out of Three

atcoder.jp

ABC074 Bichrome Cells

ABC073 September 9

ABC072 Sandglass2

ABC071 meal Delivery

ABC070 Palindromic Number

atcoder.jp

060~069

ABC069 K-City

atcoder.jp

ABC068 ABCxxx

atcoder.jp

ABC067 sharing Cookies

ABC066 ringing

ABC065 Expired?

ABC064 RGB Cards

ABC063 Restricted

ABC062 Grouping

ABC061 Between Two Integers

atcoder.jp

ABC060 Shiritori

atcoder.jp

050~059

ABC059 Three-letter acronym

atcoder.jp

ABC058 ι⊥l

atcoder.jp

ABC057 Remaining Time

atcoder.jp

ABC056 HonestOrDishonest

atcoder.jp

ABC055 Restaurant

atcoder.jp

ABC054 One Card Poker

atcoder.jp

ABC053 ABC/ARC

atcoder.jp

ABC052 Two Rectangles

atcoder.jp

ABC051 Haiku

atcoder.jp

ABC050 Addition and Subtraction Easy

atcoder.jp

040~049

ABC049 UOIAUAI

atcoder.jp

ABC048 AtCoder *** Contest

atcoder.jp

ABC047 キャンディーと2人の子供

atcoder.jp

ABC046 AtCodeerくんとペンキ

atcoder.jp

ABC045 Trapezoids

atcoder.jp

ABC044 Tak and Hotels

atcoder.jp

ABC043 Children and Candies

atcoder.jp

ABC042 Iroha and Haiku

atcoder.jp

ABC041 添え字

atcoder.jp

ABC040 赤赤赤赤青

atcoder.jp

030~039

ABC039 高橋直体

ABC038 お茶

ABC037 饅頭

ABC036 お茶

ABC035 テレビ

ABC034 テスト

ABC033 暗証番号

ABC032 高橋くんと青木君の好きな数

ABC031 ゲーム

ABC030 勝率計算

020~029

ABC029 複数形

ABC028 テスト評価

ABC027 長方形

ABC026 掛け算の最大値

ABC025 25個の文字列

ABC024 動物園

ABC023 加算王

ABC022 Best Body

ABC021 足し算

ABC020 クイズ

010~019

ABC019 高橋くんと年齢

ABC018 豆まき

ABC017 プロコン

ABC016 12月6日

ABC015 高橋くんの研修

ABC014 けんしょう先生のお菓子配り

ABC013 A

ABC012 スワップ

ABC011 来月は何月？

ABC010 ハンドルネーム

001~009

ABC009 引っ越し作業

ABC008 アルバム

ABC007 植木算

ABC006 世界のFizzBuzz

ABC005 おいしいたこ焼きの作り方

ABC004 流行

ABC003 AtCoder社の給料

ABC002 正直者

ABC001 積雪深差

2020-09-06

イ日記

こんにちは

　暑い日が続いていますね，RedSpicaです．

　先日柄にもなくインターンに参加してきました．その感想を書き連ねていきます．

1日目
2日目
3日目
まとめ

　ITで建設現場を楽にしようみたいなポリシーを持っていろいろなものを開発している静岡の会社に行きました．もしかしてこれは一意に定まってしまうでしょうか．また，日数は3日間でした．初めてインターンに参加したので普段はどんな感じなのかがわからずです(人事の方が「3日間だとあんまり来る人がいない」みたいなことを言っていたので長いのかもしれません)．

1日目

　事前にメールで参加者が1人ということを伝えられていたのですが，訪れてみると「やっぱもう1人いるよ」ということを伝えられました．

　午前中は会社の説明を聞きました．また「実際にこんな感じに使うよー」みたいな感じで機械を触らせてもらいました．初めてドローンを触って「すげー」といったお気持ちに．

　お昼休憩ではとても豪華なお弁当が出ました．オフィスがめちゃくちゃ綺麗だったりお茶を出してくれたりお弁当を出してくれたりこの会社は金持ちか？(お弁当は3日間とも出ました，すごい！)

　またお昼休憩の間に簡単な自己紹介みたいなことをしたんですが，一緒に参加した方が情報系の専門学校に所属しているらしく「(よく聞く単語)やったことあります，(聞いたことある単語)とか(知らん単語)もやったことあって(なんかよくわからん単語)も少しだけできます」という強さを見せつけられてしまいました．ぼくはもちろんそういったことは一切やったことがないので「あーえっと競技プログラミングってのをちょっとだけやってて，C++とCとPythonがほんの少しだけ書けます」といったことしか言えず，会社の方もお察しムードといった感じでした．ぼくはこの日流した涙を決して忘れることはありません．

　午後はブロックリーゲームというものを用いたアルゴリズムの研修をしました．

blockly.games

　アルゴリズムの研修と言われていたので「あ，これAtCoderでやったやつだ！」ってなるかと思ったんですが，ボコられました．ぼくは今までなにをしてきたんでしょうか．

　「学歴なんてどうでもよくて，行った学校でなにをしたかがマジで大事なんだな」とこの日以上に強く思った日はありません．

2日目

　1日目の終わりに「常識の範囲内だったら私服でいいよ」みたいなことを言われたので，この日からは私服での参加です．そもそも1日目は何も考えずに下はスーツのズボンで上はワイシャツ(ネクタイなし)といった格好だったのであまり変わらないかもしれません．

　この日の研修内容はHTMLとJavaScriptを用いたウェブページの作成，もっと詳しくいうとウェブ上で動く電卓と，自分の自己紹介ページを作るといったものでした．HTML自体は大学の授業で本当に少しだけやったことがあって「ウェブページを作ることができる何か」ということは知っていましたが，どうやって書くとかどんな感じで表示されるみたいなのは全く知りません．しかし，超親切丁寧に教えてもらえたので，ほとんど詰まることなく電卓は作ることができました．

　問題は自己紹介ページの作成です．HTMLの書き方というか，かっこいい感じのページを作れなくて困ったのもそうなんですが，自分のことについて書くことが本当に無い．人に言えるような趣味とか特技とかが欲しいなあと思いました．競プロのことを書いたり，虹のコンキスタドールのことを書いて事なきを得ました．

　2日目の総評

ぼくわかりました，JavaScriptはC++です
— 🌵卵生みらーじゅ🌖 (@asakaakasaka) 2020年7月29日

3日目

　最終日です．朝早く(自分比)に起きて大学の課題と戦っていたので少し眠かった覚えがあります．

　この日の内容はC#を使ってゲームを作るといったものでした．”ゲームを作る”といっても，グラフィックの部分はあらかじめ用意されていたので，ボタンを作ったりボタンを押したら動くようにしたりすることをC#を使って実装していく感じでした．ゲームの内容は，グリッド上を動くマシンを操作して，グリッド上に置かれたリンゴをすべて集めようというものです．

　C#は一切書いたことがなかったので不安だったんですが，会社の方々がとにかくほめる．ことあるごとにいい感じの事を言ってもらえるし，「毎回コピペのやり方もわからない人がくる」みたいなことを言っていて「そんな人も来るのか」といったお気持ちになりました．普通にゲームが成立するところまで実装したら「予定より早く進んだのでオートモードを実装してみましょう」ということになりました．ここでようやくAtCoderで習得した実装力の出番です！実家のような安心感で実装をします．クリアしたのでさらに追加の課題を与えられます，実家実装をします．クリアしたのでさらに追加の課題を与えられますが，ここで時間切れ．

pic.twitter.com/mjWWrYQpCW
— 🌵卵生みらーじゅ⛅ (@asakaakasaka) 2020年7月30日

　最後の課題はざっくりいうとこんな感じでした．dpとかをしてやるのかなーと思ったりもしましたが，偉そうにしていた割にはこれを実装する力はないです(かなしい)．

　最後に少しだけ実際の業務を見学させてもらい，これにて3日間のインターンが終了しました．インターンシップ修了証なる立派なものをいただき，お礼をして会社を去りました．

　3日目の総評

気付いてしまったんですが，C#はC++かもしれません
— 🌵卵生みらーじゅ⛅ (@asakaakasaka) 2020年7月30日

まとめ

　ぼくはこの1社しかインターンにいったことがないので他の会社はどんな感じなのかはわかりませんが，とても充実していたんじゃないかなーと思います．普段競プロをしているだけではわからない実務向けの基本的なこと，例えば「変数名をわかりやすくつける」だったり「リファクタリングをしてコードをよりよいものにする」といったことを身をもって知ることができました．

　今まで1年ちょっと競プロをやってきて身に着けたことは無駄ではなかったような気がしています，chokudaiさんいつもありがとうございます．

　競プロの実力がぼくと同じくらいの方は自己肯定感を上げるためにインターンに参加してもいい感じかもしれません．

　ブログの最後にふざけた文章を書くことを生きがいにしているのにそれっぽい文章が思いつきません，困った．

RedSpica