読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

CODE FESTIVAL 2016 に参加しました

CODE FESTIVAL 2016 参加記

予選

A

焼肉を食べていたので出なかった。

B

4完したが108分かかり落ちた。冷えた。

C

3完+部分点で通過!

夏合宿や会津合宿で「こどふぇすで会いましょう!」と言いまくっていたのが嘘にならなくてよかった。

1日目

集落を6時半に出発した。なんだかテンションが上がっていて、新幹線の中で過去問の練習コンテストをしていた。11時半頃着いた。

ちょくだいさんやsnukeさんを発見したので声をかける。仕事なので忙しそうだった。見つかった知り合いには挨拶して、席に用意されていた軽食(コッペパンのサンドイッチみたいなやつ)を食べた。

しばらくするとBGMやオープニングムービーが流れてきて、すごいという感じだった(ムービーではみんなのIDがぐるぐるしていた)

本戦

4完+部分点でパーカーを取るぞ!と意気込んでいたら3完で激冷え。

Aは今朝動画で見ていたりんごさんの挑戦状のやつだ、と思いながら解く。AC。

Bを読むが全然わからない。1 + 2 + ... + k を取れるだけとって余った分を他に振り分けるみたいなことをやっていたけどWA。30分くらい取り組んでいたけど光が見えないので、まじか……と思いながらCに行く。

Cは頂点を人と言語で分けて(人,言語)の辺を張れば2乗にならないことにすぐ気づいたので、書く。AC。↓で似たようなことをした記憶があった。

arc061.contest.atcoder.jp

Dは2つ目のルールから使う方がよさそうというのは第一感であった。modをとってiとM-iのやつを貪欲にマッチングした後余ったやつで同じ数字のをマッチングする(0と真ん中(あれば)は自分の中だけ)としたけどサンプルが合わない。それはそうで、同じ数字のペアをできるだけ残さないといけない。ということで奇数個残っているやつから貪欲に使うというのを書いたけどWA。バグってたのか見落としがあるのかわからなかったけど、Bを飛ばしていたので腹をくくってBに戻る。

Bは最大値を決めうちしてあとはいい感じにやるというのを考える。Nをdistinctな正整数の和で表すとき、最大値Mを決めると、あとはN-MがM-1以下のdistinctな正整数の和で表せればよい。そのための必要条件は N-M <= 1 + 2 + ... + M - 1であることだけど、実はこれが十分条件でもあるらしく大きい方から貪欲にやるとできるっぽかったので投げた。通った。終了5分前だった。

以後は安静にして精神の回復に努めていた。

~~~

この後touristのトークライブがあって、これまでの人生で一番「英語を聴けるようになっておけばよかった」という気持ちになった。

ここから割と自由行動になる。メシを食べないとやってらんないですよという気分だったので、メシを食べる。おいしかった(鳥を煮たような洋風のやつとチーズケーキが特に好きだった)。前々から面識のあったYazatenさんやmemphimさん、kazu0x17さん、tubo28たちと話しながら食べていた。ドラクエのマップを歩くのがIDA*だという話が出て面白かった。

歩いていたら高校の同期に出会う。kobae964さんだった。こういう場所で5年ぶりに会えるとは思っていなかったので感激する。

秋葉さんのペアプロを聴く。問題は知っていたやつだったけど、解法が洗練されていく過程がわかって面白かった。

エキシビションマッチを見る。座ってるだけじゃつまらないので立ち見であちこち動いていた。スクリーンがいくつかあってそこに各チームの画面が映し出されていたのだけれど、やっぱり強い人はコーディングも速いなという感じだった。順位表を見ながらみんなで一喜一憂したりして、結構盛り上がった。

あとこれは1日を通しての感想なんですが、りんごさんがずっと徘徊しているのが面白かった。

~~~

そんなこんなで1日目終了。ホテルがみんなバラバラで、徒歩で移動した後はお風呂に入ってすぐ寝た。

2日目

トーナメントなるものがあった。今年初の試みらしい。1日目の成績で8人ずつのグループに分けられ、グループ内で上位4人が通過(Round 1)、4人のグループ2つをマージしたグループからまた上位4人が通過(Round 2)、また4人のグループ2つがマージされ最後は各グループでの順位で表彰(Round 3)という感じだった。ラウンドは各2問で時間が30分,30分,40分と短く、しかも部分点が多い(どの問題にも3個ずつくらいある)ということで、かなり戦略性を問われるスタイルだった。

このときcamypaperさんと初対面して、最初に問題を読んでどっちに賭けるか見極めるのが大切そうという話をしていた。motiさんとも初めてお話できた。

Round 1

Aを読む。Kruskalをいじればいけそう。500点取れる気がしたので書こうかとも思ったが、とりあえずBを読む。

Bの200点はビット全列挙で、400点は区間DPっぽいことをするのかなあという気がした。トーナメントのルールとして正の得点を取らなければ次に進めないとのことだったので、とりあえず正の得点を取ろう思い200点に手をつける。さすがに手癖で書けた。10分くらいでAC。

Aに戻って500点解法(のつもりで実は200点だった)を書いた。Kruskalの判定部分に「sのグループとtのグループをマージするような辺は採用しない」を入れた。Q<=105, M<=4*105なので当然TLEするのだがQ=1の200点分は取れた。

結局、A200+B200でRound 2に進出できた。

終了後は周りの人たちと解法の議論ができて楽しかった。t8m8さんに、A問題はsとtの間にコスト0で辺を張ると考えてよいという話を聞いて、天才かなと思った。

Round 2

Aを見てすぐ「確率だ!逃げろ!」と思ったのでBに行く。

Bは200点なら書けそうな気がしたので書く。4分でAC。順位表を見るとAの200点が解かれていたのでAに戻る。

Aを読むと200点がド自明でビビる。AC。ここまで8分。あとはAの300点を考えていたが、間に合わず。

またA200+B200で、Round 3に進出できた。

Round 3

Aは問題文がぱっと見よくわからなかったのでBへ。

Bは400点分ならセグ木やるだけを感じる。M...Mm...mということは最初に幅固定の最大値を取って、最後にそれらのminを取ればよい。ACしたけど17分くらいかかっていたらしい。

Aの100点は大きい数字から採用すればよさそうと思って書いたがWA。200点はDPだろうなと思うもうまく落とし込めず、そのまま終わった。

結局Bの400点だけで入口から1番近い列グループの1位になってしまった。akiさんがBの満点解法を書いていたらしいので、それが通れば圧倒的に負けていた。

今回はラウンドを1つ勝ち進むごとにステッカーをもらえてそれをコンプするとCODE FESTIVALのロゴが出来上がる(+ちょっとイラストがある)という感じだったのだが、そのステッカーのコンプ&表彰で登壇をさせてもらえて光栄だった。

トーナメントは、競技プログラミングの「競技」面を強く感じるイベントだった。普段は自明な部分点を取っても学ぶことがないと思い満点を考えにいくことも多いが、今自分が出せるものを最大限活かして勝ち進むというのも楽しいと感じた。GCJとか割とそんな感じなのかもしれない。

~~~

昼を食べる。お弁当争奪戦でキジ肉弁当なるものを珍しさから選んだが、肉が硬くてあまりおいしくなかった。海鮮にすればよかった。

トイレに行ったりしていたらきゅうりさんのライトニングトークを聞き逃した。ちょくだいさんのを立ち見していたけど、ひたすらテンションで押し切っていて面白かった。

りんごさんの挑戦状2(トークライブ)を見た。りんごさんが出すよくわからない問題に競プロ界の強い人たちが答えるというイベント。いろいろゆるくて好き(競プロ界隈のアットホームさを表していると思う)。今回の解答者の皆さんはhogloidさん、semiexpさん、snukeさん、tozangezanさんだった。snukeさんが自己紹介でクソなぞなぞコンテストの戦歴を語っていて面白かった。世界地図のやつを見ていたら皆さん地理力高すぎてビビった。

そして最終イベント、チームリレーへ。

チームリレー

大人数での団体競技ということで不安もあったが、いざ始まってみると結構楽しめた。チームはKチーム(黒)で、海外勢はsevenkplusさん。戦略としては順位順に1問ずつ割り当てて、必要なら適宜相談しながらやるという感じだった。

自分はとりあえずA問題を解いた。さすがにやるだけだったのですぐAC。帰ってきてからは色々ちょっかいを出していた。Cを考えていたutsubo_21さんにシミュレーションだが実装はどうするのが楽だろうと聞かれ、vectorを2段持ってバケツリレーしていくのが良さそう的なことを言った。Fを、担当していたnkshnさん&既にBを通していたt8m8さんと一緒に考えた。切る回数を最大化するには 1, floor((N-1)/2), ceil((N-1)/2) と切るのが良さそうで、これを使えば二分探索で解けそうということを言った。あとはパソコンの順番が回ってくるまで一緒に紙コーディングをしていた。割と翻弄してしまって申し訳なかった。

以降は強い人たちが既に解法を作りきっていてあまりすることがなかったので、レッドブルを飲んでいた。後半の問題の解き方をdrafearさんやsortreewさんに教えてもらったり、Kを解くsevenkplusさんの姿をみんなで見守ったりしていた。J問題が面白いと思った。

~~~

あとは表彰式。川柳とか太鼓の達人とかいろいろあったけど自分はノータッチだったのでひたすら拍手を送る機械になっていた。書道コーディングでまさかの芸人書道家が出てきて面白かった。natriumさんが「劣モ」をリクエストしていてさすがだったのと、「十億七」は普通にかっこいいので欲しかった。

表彰式が終わるとついにこどふぇすも終わりで、関西勢と一緒に新幹線に乗って帰った。駅弁の牛肉弁当がおいしかった。

まとめ

CODE FESTIVAL、とても楽しかった。コンテストは良問揃いだったし、一口にコンテストと言ってもいろんな楽しみ方があるのだと思った。イベント面でも有名な人の話を聞けたりして貴重だった。

競プロ界の知り合いたちに再会できたのもよかったし、初めてお話しできた方はたぶんもともと名前を知っていた人だけでも10人以上いて、またどこかで会えるといいなと思った。今回お話しできなかった人もいるが、競プロをやっていればまたいつか出会えるだろうからいいということにした。

ぜひ来年もやってほしい。もしやるならばぜひ出たいし、出られるように頑張りたい。