CODE FESTIVAL 2016 Final 参加記録

日本最大のオンサイトプログラミングコンテスト、CODE FESTIVALに参加した。プログラミングコンテストと言うが、実際にはアルゴリズムコンテストという感じ。僕はドイツ留学中に、このコンテストの予選を突破した。

http://intelhamko.hatenablog.com/entry/2016/09/26/111113

このコンテストは、大学生・大学院生・未就業者を220人（！）集めて開催される。人数が多いので、予選突破が容易である。むしろ普通の人間がこれ以外でオンサイトに参加するのは困難だと思う。220人のアルゴリズムのスペシャリスト（主にTwitterなどでよく見かける人）と話す機会であった。実際に僕はTwitterのみで知り合いだった、多くの優秀なプログラマと会話できた。

コンテストは主に3つあった。(1) 本戦。10問3時間。1600点以上でパーカーがもらえる。 20位以上で賞金がもらえる。 (2) トーナメント。本戦の近い順位の人で戦い、勝ち残る。2問30分。突破ごとにステッカーがもらえる。(3) チーム戦。11人チームで、11問の問題を90分で解く。チーム対抗で戦う。パソコンはチームで1台。1人1問しか実装してはならない。

全コンテストを通じて、結果は散々だった。自分のアルゴリズム力もプログラミング実装力も全然ないことを自覚した。コンテスト中、ずっと帰りたかったレベル。

本戦では、1500点でパーカーがもらえず、136位/220人だった。10問はAからIまで番号が付いている。A-Dまではミスがなく、66分くらいでそれなりにすんなり解けた。ここまでで1500点だった。パーカーゲットには、Eの部分点かFかHの部分点を解く必要があった。Eが、点数も低く簡単そうだったので、2時間くらい取り組んだが、全く解けなかった。Eの部分点は明らかに凸凹していそうだったので、絶対DPだろうと思いながらも、思いつかなかったので嘘貪欲を書いて死んだ。

解けた問題は以下。A問題は、全探索＋文字列比較。B問題は、 ${O(n^2)}$ までの値で必ず構成できるので逆から自明に貪欲。C問題は、対応逆にしてUnionFind。D問題は、mod Mの世界でカウントして、偶数個あるものはなるべく残したいので、奇数個の数字を優先に消化していく貪欲。

http://cf16-final.contest.atcoder.jp/submissions/991410

http://cf16-final.contest.atcoder.jp/submissions/991690

http://cf16-final.contest.atcoder.jp/submissions/991995

http://cf16-final.contest.atcoder.jp/submissions/993120

トーナメント戦では、0点で1回戦敗退だった。2問はAからIまで番号が付いており、部分点が多く設定されていた。初め、400点くらいが突破ボーダーかな、と思っていたが、ボーダーは100点（0点でなければ良い）だった。本番で、僕はA問題はグラフで筋肉が必要そうだったので、簡単そうな桁DPっぽいB問題にとりかかった。これは ${O(n^3)}$ DPが自明だったので、実装しようとした。しかし、バグって実装が終わらず0点となったしまった。しかもバグの原因が本当に大馬鹿で、(string)"123">(string)"24"だと思い込んでいたせいだった。コンテスト後20分くらいデバッグして、B問題の ${n \le 100}$ 制約のみACさせた。dp(i, j, h) = s[0:i)にちょうどj回カンマを挿入して、最後にh文字カンマが入っていない時の最大値の最小。