会津合宿2017 参加記
9/18~9/20の2泊3日で、これに行ってきました
競プロオンサイトイベントはCODE FESTIVALしか行ったことなかったので、とてもワクワクしながらオンサイト行きました。
会津大学に初めて行ったんですが、自分が通っている大学と比べてかなり景観が良くて、自分もこういう感じのキャンパスに通いたいなってなった*1。
台風一過で、気温もちょうどよく、天気も良くてかなり過ごしやすかったです(小さい頃福島県に住んでいたのでなんとなく分かるのですが、夏はめちゃくちゃ暑いし冬は雪が大量でつらそうなのでかなりいい時期だと思います)。
ちなみに、宿は同じ大学の後輩2人と3人で泊まりました。 自分は、普段結構眠れずに夜更かしをしてしまう*2ので夜みんな寝る時に全然眠気こなかったらどうしよう...とか思ってたんですが、毎日宿に着いたらほぼすぐ寝られました。
各日のコンテストのチーム分けは、組みたい人がいればその人と組んで、あとは(バランスを取ると言う意味で)レートが高い人が低い人の名札を2枚引いてチームを組むという感じで決められました。
Day 1
コンテスト
チームはACPC_shake_daaaaaというチームでshakeさんとtsukasa_diaryさんと一緒に参加しました。「シャケだー」は「日常」ネタらしいです(「日常」を断片的にしか知らず)
tsukasa_diaryさんはこの合宿のコンテストではコーディングしない縛りをするとのことだったので、shakeさんと自分がコーダーになるという形になりました。 とりあえずshakeさんにA、自分はB、tsukasa_diaryさんはC以降という感じで読み始める。Aをshakeさんが書いている間に、Bも方針が立ったので、Aが終わったらそれをshakeさんに伝えながら書いてもらう。で、ちょっとバグらせたりなんだりしている間にtsukasa_diaryさんからCとDの解法が降ってきたので自分が実装マンになる。後はEとかFとかを考えている間にうーんとなって終了してしまった。フローやっぱりまだ練習が足りない...という反省。ABCDの4完でした。
解説の時、最終問のヤバさがヤバすぎて度々謎の笑いが発生していた。
懇親会
駅前の中華料理屋で懇親会が行われました。会津の人とか立命館の人とかと交流をした(雑すぎる)
後はACPCの顧問的なポジションの先生が隣だったので色々お話をした。「早稲田、最近ICPC参加チーム増えてますよね、早稲田でもコンテストやらないんですか？」みたいなことを言われた。一応やんわりと企画してはいますが、運営者側が現状4人で、今回の3日間(立命館・会津・北海道大学)の作問チームのお話とかを聴く限り、やっぱり4人で準備するの無謀でしょ...みたいな気持ちになったので、今すごくどうしようか頭を抱えています...
この日は朝早かったのもあって、即寝した。
Day 2
コンテスト
チームはACPC_fitというチームでfuu32さんとtuki_remonさんと一緒に参加しました。
A,B,C(自分)とそれぞれ読み始めてAもBもいけそうと言う感じなので順番に書いてもらう。が、Bはサンプルが合わなくて自分もCを通した後で一緒にバグを探すことに。連休との距離が年をまたいでるときにおかしいことに気づいて、直してもらった。次に、Dはfuu32さんと一緒に考えて自分が方針を立てたので、どっちが実装しようかってなったけど色々ややこしいので自分がやることに。
その後、EとかFを読むけど全然方針が立たずに「？？」となる。Gも読んでみたけど実装大変だし、最後のDPが早くする方針が立たないからとりあえず置いておく。この辺で、他の問題を読んでもらっていたチームメイトからIは二部マッチングで、Lはセグ木でいけそうな気がするというコメントが来たので、自分がフローの写経をしたり、セグ木の写経をする。
最後1時間で、なんとかEとF(小さい方で実験したら何となく分かった)を通した。ABCDEFILの8完でした。そのうちのAB以外の6問を自分が実装していたので、もう少しチームメイトに実装を任せるということをした方がよかったのかな...という反省感があります。この辺をどうするべきかが悩ましくて、普段自分のチームだと方針が立った時に(幾何以外は)自分に実装が降ってくることが多いのですが、その辺の振り方が難しい。
懇親会
この日は、この合宿のスポンサーであるRCOさんのおかげで参加費無料の懇親会が開催されました。(ありがとうございます(｡>﹏<｡))
だいたい半分くらいでお酒飲む席と飲まない席に分かれたんですが、自分は飲む側の席にいて、大いに盛り上がりました(内容は書きません*3 )
この日も早稲田でコンテストやらないんですか？みたいな話になって、4人だけは現状で集まってるっていう話をしたら、どっかの大学とコラボしてもいいんじゃないですか、と言われてじゃあどことかなあ...って言ったら「慶応でしょ」みたいな話になって面白かった。確かに、そういう案もあるなあって思った。ただ、慶応のICPC参加者を全然知らないので自分からはコンタクトできない...また、もし他にも人が足りないみたいなところあればぜひ声を掛けて下さい...
この日の夜はこどふぉ(div2)があったので、かるく酔っていたけどunratedなので宿で参加したりして過ごした。
Day 3
コンテスト
北海道セット(3時間)でした(コンテストページ)
チームはACPC_Anzio_High*4というチームでrikaさんとYang33さんと一緒に参加しました。A,B,Cとそれぞれ読み始めて、Aはすぐ行けそうなのでやってもらう。Cはすぐには方針が立たなかったので、AをYang33さんに通してもらった後、一緒に読んでもらう。
Bがとても辛そうなので、一緒に考察する。rikaさんが、領域内の格子点の数みたいな考察をしていて、この個数を高速に数えたいなあと思うと、公差の方の軸で切ってみるとその直線上に並ぶ格子点の個数が等差数列になってそうな感じが見えたので、結局この等差数列が初項、公差、項数は何なのかをrikaさんに計算してもらう。
Cが通る頃にBの計算が終わっていて、とりあえずこの考察が合ってそうかどうかを確かめるために自分がpythonで等差数列の和を求める関数を書いてチェックする。合ってそうなので、実装を任せようかと思ったのだが、この等差数列の和を求める関数が実質答えになるので、そのままメイン関数も書いて自分が提出する。modとかオーバーフローとかに苦心する必要がなく、python最高という気持ちになる。
Eは問題を読んだYang33さんから「2次元BITを使いそう」という話を聞いて、自分も読んでみたらいけるとなったのでYang33さんに書いてもらう。自分は2次元BIT持ってなけど、Yang33さんは持ってて、すぐに写経が終わったので、そこからのクエリ処理とかをペアプロする。
残り1時間でFとGが残っていて、Fは「足し算だったらよくありそうな問題だなあ」って言ってた(logとれば足し算になるという発想は無かった...)。Gは、とりあえず普通に行列累乗するDPは方針が立って、制約怖いけど投げたらやっぱりTLEする。そこから、「行列累乗 高速化」とかでググり始める。すると、Yang33さんが巡回行列の積を高速に計算する方法を見つけて、自分の行列累乗の行列も巡回行列になっていて「おおー！」ってなってそこから30分で頑張って通した。
まとめ
初めて合宿系のイベントに参加したんですが、とても楽しめました。毎日いろんな人とチーム組んでやるのが良く、若干チームを組まなかった人とは交流が少なめになってしまったのは残念ですが、やっぱりチーム戦は楽しいですね。
あとは弊学でもコンテスト開きたいですね...今年ICPCに10チームも参加していたので、どこかに人はいると思うんですが(観測はできていない)、会津とか立命館とかの様子を見ていて、競プロに興味がある人が集まっているのがいいなあと思ったので、うちも集まったらいいんじゃないかなと思います。なので、興味がある人は最近できたPDCとかにコンタクトしてみたら良いと思います。
会津、とても充実していたので、来年もまた参加したいです。春の立命館合宿も行ってみたいですね。
会津大学の皆さんありがとうございました！
