競プロ初心者のためのCODE FESTIVALの楽しみ方

この記事は、 eeic Advent Calendar 2016 その2 の5日目の記事として書かれたものです。

競プロ初心者が運良く CODE FESTIVAL 2016 の予選を通過し、11/26-11/27の本戦に参加してきた日記です。予選を通過する方法と本戦の楽しみ方を紹介します。Advent Calendarに書くものとしてふさわしいのか疑問ですが、大目に見てください。
注意点:
1点目: この記事では言語仕様の話やアルゴリズムの話はしません。分からないので。
2点目: プロの皆さんは温かい目で見てください。
3点目: 記事が結構長いです。コンテンツの量が多かったので。
4点目: CODE FESTIVALというのが正しい表記です。間違っても"CodeFestival"などと書かないように注意してください。よろしくお願いします。

CODE FESTIVAL とは

CODE FESTIVAL とは、RECRUIT / Indeedが主催するプログラミングコンテスト(プロコン)のイベントです。プロコンと言うだけではかなり幅広い意味ですが、ここでは特に競技プログラミング(競プロ)のコンテストのことを指します。競プロとは一言で言えば、指定されたフォーマットの入力に対して条件を満たす出力を返すプログラムを早く正確に完成させるゲームです。(ここまでテンプレ)
システムはAtCoderのオンラインジャッジを使用しています。AtCoderとはプロコンを定期的に開催したり、今回のように他の会社にシステムを貸し出したりしている会社です。ちなみにこの社長が本戦会場で問題の解説をしてくれたりライトニングトークをしたりしていて生で見られました。
参加資格は、日本在住の｢学生（高専4~5年生、高専専攻科、専門、短大、大学、大学院）または既卒4年以内の未就業者｣、参加人数は合計220人となっています。ただし今年から海外在住の学生も20人まで参加できるようになり、国際コンテストとなりました。なぜ20人に制限されているかというと、そうしないと参加者が海外の方ばかりになってしまうからです。
参加資格をよく見てみると、社会人はもちろん、高校生以下のつよい人々(西日暮里の有名な高校とか神戸の難しいところとかに多い)も本戦に参加できないことが分かります。つまりチャンスということです。私が競プロを始めたのがちょうど1年前で、その間ブランクも多かったことを考えると、興味のある方は今からでも始めると来年のコドフェスに参加できます。
まとめると、(他のコンテストと比較して)日本の大学生が参加しやすいオンサイトのプロコンです。こういうイベントは他にないと思うので、興味があれば是非。

予選

リクルートのウェブサイトで申し込みをしたら、予選コンテストを通過する必要があります。予選は複数回実施され、いずれかで通過すればOKです。今年は2時間で5問が出題されるコンテストでした。
予選A 予選B 予選C
予選Aでは、4問以上解いた人と、3問解いた人の中で早かった人が通過できました。リンクから問題を見てみてください。3問目までは簡単っぽいことが分かると思います。3問を14-15分で解ければ勝ちです。BとCについては、既に通過した人はカウントされないので、Aより通過難易度は下がっていたと思われます。普通にアルゴリズムの勉強をしている人ならきっと通過できるでしょう。

以下は日記です。

(1日目) 会場入り(12:00)

遅刻した。(12:15)
席に着いたら弁当が置いてありました。殻が付いたままのゆでたまごと、サンドイッチとあと何かがあったのだけは憶えています。(本戦中に食べました)

(1日目) CODE FESTIVAL 2016 Final

問題はこちら
本戦です。配点が以下のようになっていて、1600点以上とるとCODE FESTIVAL パーカーが貰える、というものでした。 パーカーを貰える最小限の得点の取り方は、ABCDe, ABCE, ABCFの3通りが考えられます。(小文字:部分点)

(カッコ内:部分点)

ABCまで解き、Fはグラフっぽかったので早々に諦め、Dを捨てEの満点を狙おうと考えました。
駄目でした。Eの部分点すら取れませんでした。いつの日かパーカーをゲットし必ず中級者を名乗ってやる、と固く心に誓いました。
ちなみにDはそんなに難しくなかったので冷静な思考ができる人はまずそっちを解いていたようです。

(1日目) tourist氏 講演

tourist氏とは、ベラルーシ出身、現在ITMOというロシアの大学の学生で、競プロ界では知らない人はいないレベルに"強い"方です。(私は競プロ界の人間ではないので知りませんでした)
彼はプログラマの両親の影響で7才のときに競プロを始めたそうです。7才。
事前にTwitterで収集した質問にtourist氏が回答するという形で1時間ほど続きました。｢今まで行ったことのあるカリブ海の島で一番好きな島はどこですか｣という質問があったこと以外はよく憶えてないです。(カリブ海は行ったことないそうです)

(1日目) 本戦問題解説

会場内でchokudaiさん(AtCoderの社長)が本戦の問題の解説をしていました。同時にラジオで放送されていたみたいです。

chokudaiさん｢◯◯知ってますか？ 皆さんさすがに◯◯は大丈夫ですよね？｣
周りの人々 (頷く)
私 (知らん……)

みたいなのがあって勉強しなきゃなあと痛切に思いました。

(1日目) 秋葉拓哉氏 トークライブ

秋葉さんがペアプログラミングするトークライブ。コーディングしている人が誰だか分からなかったのですが、その隣で秋葉さんがツッコミを入れていました。
倒すべき敵は｢チョク=ダーイ｣(第1形態、第2形態、最終形態)で、問題とそれぞれの制約は以下のような感じでした。(細かい数字は違うかも)

チョク=ダーイとW×Hブロックの板チョコを使ったゲームをする。プレイヤーは長方形の板チョコを、2つの長方形に分割されるように折って割る。次のプレイヤーは2つに分割されたチョコのうち一方を選び、それを2つに割る。選ばなかった方は捨てる。これを繰り返し、最後の1×1のチョコ片をとった方が負けである。チョコの高さと幅は常に整数でなければならない。自分が先攻であるとき、自分が勝てるかどうか判定せよ。

制約
第1形態 1 ≦ W, H ≦ 5
第2形態 1 ≦ W, H ≦ 100
最終形態 1 ≦ W, H ≦ 10⁹

ライブでは時間ギリギリでチョク=ダーイ最終形態を倒すことができました。やったー！
(なおchokudai氏とは別人なのでそこはよろしく、とのこと)

(1日目) 夕食

会場にビュッフェコーナーがあり、各自欲しいものをバイキング形式でとりました。メニューは以下。

寿司の、なくなる速さ。
途中で食べすぎて気持ち悪くなってきた私は、"イタリアンサラダ"というのが小さなプラスチック容器に一口サイズの牛肉とレタスとオリーブの実が入っているもので食べやすかったので、それを無限にヒョイヒョイ食べていました。

(1日目) CODE FESTIVAL 2016 Exhibition

問題はこちら

本戦上位陣によるエキシビションマッチ。3人1チームのチーム戦で、ACM-ICPC形式(PCはチームで1台のみ)、1時間で2問というコンテストで、各チームの部屋の様子は会場のスクリーンに写されています。日本チーム、海外チーム、ゲストチーム(Indeed社員)の3チームで、おそらく大方の予想は海外チームの勝ち、であり、開始前のコメントも

司会 ｢勝てると思いますか？｣
日本チーム ｢勝てないと思います｣
海外チーム ｢予測不可能だと思います｣
ゲストチーム ｢皆さんの予想通りだと思います｣

のような感じでした。
会場も同じような空気だったのですが、40分経ってもどのチームも得点できず苦戦していて、結局開始50分でゲストチームがBをACした以外に得点はありませんでした。そんなわけでゲストチーム優勝ということで、本当に予測不可能でしたね。
個人的に印象に残っているのは、オープンコンテストのほうで5人の方がACを出している点です。チームを組んで協力していたのかもしれませんけど、それでもすごいなあ、と。

(2日目) 会場入り(08:00-09:00)

遅刻しませんでした！(08:20)
席に着いたら弁当が置いてありました。内容は鮭おにぎり、牛肉の佃煮(？)のおにぎり、唐揚げ、たくあん、ゆでたまご(殻無し)でした。
あとディスプレイにDoS攻撃するように指示がありました。公式DoS攻撃というセンセーショナルなワードの誕生です。

(2日目) CODE FESTIVAL 2016 Elimination Tournament

問題: Round 1 Round 2 Round 3

おそらく去年まで｢あさプロ｣と呼ばれていたもの。今年は勝ち抜きトーナメントになっていました。
Round 1では本戦の順位が近い8人のグループ内で勝ち抜きを行い4人を選ぶ。Round 2では、隣のグループとマージして同じことを繰り返す。最終的な勝者は会場の約1/8となる、というルールです。
結果ですが、私は駄目でした。勝つとシールが貰えたので悔しいです。

(2日目) 昼食

弁当が5種類ほど山積みしてあって、各自好きなものを1つ選ぶというもの。私は焼き肉弁当をいただきました。またたまごかよ。

(2日目) ライトニングトーク

いろんな人が10分ぐらいずつ話していました(たぶん)。私は最後のchokudaiさんのトークしか聞けませんでした。そのお題は｢権威あるプログラミングコンテスト ICFPC2016 で堂々の世界第1位に輝いた私が教えるハンドスプリング徹底入門｣

ハンドスプリングとは地面に手をついて前転とかやるアレです。 曰く、TopCoderのオンサイト決勝などでは選手入場フェーズがあり、大抵の選手は両手でガッツポーズをとるなどショボいことしかしない、しかしそこでハンドスプリングを行うとどうか？ 手軽に一芸披露することができる！ ハンドスプリングは競プロerに有用！！！ という論理らしいです。(普通はそういうオンサイトに行くこと自体無いのですが)
手順は次の通り。

1. 手を上に上げる
2. 手を勢いよく地面に振り下げる
3. 脚を勢いよく上に上げる
4. ぐるっと回る
5. ね、簡単でしょ？

(2日目) CODE FESTIVAL 2016 Relay

問題はこちら

チーム対抗、リレー形式のコンテスト。1チーム11人(うち1人は海外勢)で、各チームにコーディングスペースが与えられ、11問の問題をかわるがわる解く。同時に複数人がコーディングするのは禁止で、必ず1人が1問を実装しなければならない。誰がどの問題を解くのかは自由だが、一度決めた担当は変えてはならない。 チームのスペースでアルゴリズムなどの相談をすることが可能で、実質的に各メンバーに問われるのは実装力だけ。ただしこれもコーディングスペースからチームスペースに戻って言語仕様などをメンバーに聞くことが可能。
以上のようなルールで、20チームの対抗コンテストとなりました。海外の人とのコミュニケーションが上手くとれるか不安だったのですが、始まってみるとチームで話し合いながら問題を片付けていくのが楽しく、英語もまあなんとか伝わるので杞憂でした。というか海外の人は大体の問題の答えが分かるので、こちらで分からなければとりあえず英語で聞いてみる、というのが効率的で、そういうゲームでした。
と、ここまで読むとなんだかすごくチームに貢献したように思えますが、私が実装したのは2問目、しかも本来5分もかからないはずのものを10分ぐらいかけて書いたようなレベルであり、賢い私はそのことをちゃんと自覚していたので、チームでは積極的にゴミの片付け等の雑用を行っていました。
チームの人がつよい人ばかりで、最終的に全ての問題をACすることができました。何もしていないのにすごい達成感を味わうことができました。

(両日) その他のコンテンツ

オープン控室

要するに休憩スペース。暇な時はここでずっと｢セット｣というカードゲームをしていました。私は初めて知ったのですが、競プロ？数オリ？界隈では有名、人気っぽいです。他にも色々なボードゲームが置いてありました。

書道コーディング

半紙に墨汁で競プロっぽい作品を書くコーナー。創造性。

コード川柳

Twitterでハッシュタグを付けて競プロっぽい川柳をツイートする。センス。

体力測定

背筋とか垂直跳びとか。よい競プロはよい体力づくりから。

太鼓の達人

ランキングの課題曲は残酷な天使のテーゼ(難易度:むずかしい)。トップ層は確か70万点台でした。

UFOキャッチャー

CODE FESTIVAL のロゴが入った手ぬぐいやらタオルがゲットできます(ゲットできるとは言ってない)

おわり

というわけで、初心者が気をつけるべき唯一のコンテンツはチームリレーです。ここさえ上手く乗り切ればあとは適当でもなんとかなります。
コドフェスは競プロ以外にもいろいろ遊べて初心者でも楽しめるプロコンイベントです。参加できるのは(ほぼ)学生のうちだけで、コンテストを通して学べることも多いですし、あわよくば中級者になれるかもしれないので、是非みなさん参加しましょう。