学習の栞

学びたいことと、学ぶべきことと、学べることの区別がついてない人間の進捗管理

CODE FESTIVAL 2014 参加記

プログラミング 競技プログラミング

乱文・長文注意。

CODE FESTIVAL2014に参加してきました。オンサイトコンテストに参加するのはJAG合宿以来で三度目です。

 

CODE FESTIVAL予選前
CODE FESTIVALが開催されるらしいという情報が出たのは夏休み突入前で、交通費全額支給+本選人数200名というコンテストが開催されるらしいという話が出た時点でtwitterはお祭り騒ぎでした。twitterで「ある程度のレベルがあるプログラミングサークルは部員旅行に連れて行ってもらうぐらいな気分でいい」という話があったので、自分の所属するプログラミングサークルの夏休みの活動目標にCODE FESTIVAL予選通過が設定された。

 

CODE FESTIVAL予選
予選A104位通過。D問題の満点解法が貪欲だろうという検討はついたが、解法を詰めるのに時間がかかりそうだったのでさっさと部分点を取りに行った。Dの満点解法を実装しようとして初期化ミスでprintf消すと動かない事案を踏んで1時間つぶしたのは悔しかった。結局330点だった。
予選Bは全完で56位。私は実装苦手な人間なのでDの部分点までに時間をかけすぎてDの満点を取るまで散々な順位だった。とりあえず予選Bでも予選通過順位に入れたので良かった。

ちなみに、所属しているプログラミングサークルの部員で、予選に参加した人は8割くらい通過していた。リクルートさん部員旅行ありがとうございます。

 

CODE FESTIVAL前日
3限の講義が終わって東京へ出発。前泊の宿泊費も持ってくれるとはリクルート社恐るべし。本選参加前アンケートで保安検査場の通過やら手荷物の受け取りやらを考慮したら最短で3時間以上かかるな。という感じだったが、実際には会場近辺のホテル到着まで4時間以上かかった。前泊申請しといてよかった。
R&Bホテル上野広小路に宿泊だった。明らかにCODE FESTIVAL参加者だなという人たちが居る。しかしコミュ障をこじらせてどうこう。

JAG夏合宿のときもそうだったが、競プロ勢というのは一目でそれとわかる独特の雰囲気を持っているらしい。

 

CODE FESTIVAL一日目

本選前

受付に立っていたのがJAG合宿でチームを組ませてもらったyuustiさんで「あっ」という感じになる。交通費精算の書類に判子を押したあと、CODE FESTIVAL Tシャツをもらう。初めてのプロコン系Tシャツで嬉しい。6完してパーカー獲得するぞと意気込む。twitterのぞいたら向かいの席にYazatenさんが居ることが分かりお話してた。

 

開会式

なんか格好良い映像が流れる。twitterではどんだけ金かけたんだという雰囲気に。しかも後援がアカデミック。CODE FESTIVALやべぇという雰囲気になる。indeed社の方がお話を英語でする。英語できないのでtwitterに集合してた。適当に拍手を送る。
開会式終了後、OpenContestとLA賞がらみのルールの穴が突かれる。ルールの穴が仕様になった。


本選
5完で150位でした。D問題ではまった。辛い。B-D問題で1回ずつWAを叩いていて作問者が用意した落とし穴すべてに落ちたり、自分で掘った落とし穴に落ちたりしてた。

A,Bはやるだけ。B問題で制約|S| <= 3000を見て、intに入るな。intで大丈夫と思ったのはダメだった。Sは数字の列でした。Sをstringで受け取り無事AC。これで10分無駄に。
C問題、fが単調増加だったら嬉しいなと思って単調増加であることを示そうとするがうまくいかなかった。小さい数で実験すると単調増加のように見えたので、単調増加と仮定してプログラムを組む。ループまわして確認してみるとfが単調増加だったので提出したらACした。

D問題、はまった。後回し。パスカルの三角形を描いて問題文をよく読むと入力受け取って足し算して吐き出すだけ。この問題のACが142:23。辛い。

E問題。明らかにDP。ぬるっと実装してAC。

私を含む多くの人が解けたのはこの五問。5完が110人ぐらい居た。

5完した時点で残された時間は30分ちょっと。J問題はO(1)解が存在しそうな雰囲気だったので、思いつけば実装は簡単だと判断してJ問題に挑む。結果爆死。

 

休憩

大学の先輩や同期と、あの問題はああやって解いたとか、パーカー取れなくて悔しいとかそういう話をしていた。近くにkoyumeishiさんを見つけたけど、コミュ障をこじらせてどうこう。

 

解説

A-D問題はやるだけ的な扱いを受けていた。E問題からちょっと難しくなりますねーみたいなことをちょくだいさんが言ってたけど、個人的にはE問題はB問題の次ぐらいに簡単だったのでなんかなー。小さい例で実験するのは大切だと思い知らされた。F問題の解法を聞いて、JよりFに取り組むべきだった感じもする。

 

TALK SESSION 01
ちょくだいさんを見に行く。アルゴリズム擬人化の話だった。それなりにぶっ飛んでた。「Brute ForceでTLEしたら実装したお前の責任」らしい。ビームサーチといわれても何のことだか分からなかったけど、説明を受けて再発明したアレだと気付く。ビームサーチなんて名前で呼ばれてたのね。

 

Food Challenge
ごはんを食べたかったので、FoodChallengeした。診断人さんのニコ生を後日タイムシフトで見て、FoodChallengeしてる場合じゃなかったと思った。FoodChallenge中は同じ大学の先輩や同級生、そしてYazatenさんと本選の感想だったり、AOJの進捗どうですかとかそういう話をしていた。そこにちょくだいさんが現れてお話できて嬉しかった。本選Bで入力間違えてintで受け取ったとかいう話をしたら、sampleに3000を超す入力あったじゃんと怒られた。sampleは注意深く読みましょう。絶対に。

 

LIGHTNING TALK 01
肉LTと幾何問題の美しい解き方について。肉LTは「肉はアルファベットより数字に拘れ」という話だった。幾何問題の美しい解き方はコンピュータジオメトリに載ってるらしい。

 

TYPING

LT終わってぶらーっとしてたらTYPINGやってみませんかーと言われてやってみた。ミスタイプでGAME OVERしました。（翌日リベンジ。5分弱でクリアしました。）

エキシビジョン
本選上位者が実況付きでコーディングをするという企画。amylase伯爵の実況・解説もあってとても面白い企画だった。そして、コーディングを眺めながら問題の解説を受けるだけで盛り上がれる観戦者もなかなかだった。準急さんがやべぃ。slが走っていたり、コンテスト中にブログを更新したり、たこ焼きclerを投げたりと、エキシビジョン出場者の遊びも見ていて面白かった。

CODE FESTIVAL二日目

あさプロ

「朝からプロコン」の略らしい。コンテストページには「asa!」の文字列。CODE FESTIVAL 前にはtwitterで「あさプロ（朝までプロコン）」の文字列が流れていたりしたけど、朝までプロコンやってた人居たのかな。朝までプロコンは来年に期待ですね。会場入り口で配られた、チーム対抗早解きリレーのチーム割から、隣の席がichyoさんらしいことが分かる。やはりコミュ障をこじらせてどうこう。
あさプロはeasy, middle, hardの3つのコンテストが存在して、二問づつ問題がかぶっているという説明を受けた。本選150位だったので、middle最底辺として参加。結果は2完の16位でした（大躍進）。参加者のレベルが制限されているとはいえ、AtCoderの順位表一ページ目に名前を載せたのは初めてなので嬉しかった。

あさプロmiddle
A問題は両側からdijkstraやるだけ。類問がQUPCで出てました。QUPCでこの問題の類問を作問してたkyosさんは爆速で提出していたはずである。

B問題は貪欲にやるだけ。ちょっとだけデータ構造の知識が必要。

C問題は本番中に解けなかったのですが、あとから考えてみたら遷移確率行列の積を繰り返し二乗法をつかってとるだけだった。twitterでは誤差どうこう言われてたけど、コンテスト終わって実装した感じだと大して誤差に気を使う必要は無かった。遷移確率行列の考え方は大学の講義で習っていたのに解けなかったのは情けない。情報理論の＊＊先生ごめんなさい。

D問題はDPだったらしい。帰り道、空港まで行く電車の中でDarseinさんに教えてもらった。この日の個別指導塾で「ぽよぽよがN*L*Lで通ったんだけど、、、」という質問が来ていたらしく、Food Challengeしていたらamylase伯爵が個別指導塾のほうに呼び出されていた。

本選でA問題のLA賞狙いに行った同級生のn*kollsonとかいうやつが真面目にやっていれば本選151位でeasy全完（1位）＋middle2完(16位＋）で両入賞だったのになーとぼんやり考える。

 

TALK SESSION 02
ちょくだいさんと坂本一憲さん（国立情報学研究所助教）のトークセッション。プロコンがらみの雑談で盛り上がったあと、AI Challenge用のAIをペアプロ。次に出す手を選ぶとき、相手が何を出すかの予測を入れるために、次の手を決定する部分を複数回ループさせるというテクニックを学んだ。chokudAI Contestが走っていたり、サーバー落として「これがレッドコーダーの撃墜力だ（ﾄﾞﾔｧ」と言ったりと笑いもあって面白かった。

 

書道コーディング

面白そうな企画だと思ったので参加。
#defien WA AC

#define TLE AC

#define MLE AC

#define RE AC

と願望を書いた。#define CE ACが抜けていると指摘されたりした。

 

LECTURE 02
あの秋葉さんのトークということで参加不可避だった。開始時間ぎりぎりに入室した人は立ち見だったので、早めに会場に行っておいて良かったと思った。あきばやばかった。競プロの練習方針について聞けたり、サイン貰えたりしてよかった。匿名質問できる制度大切ですね。

 

チーム対抗早解きリレー
チーム11(チー無名)で参加。C問題を担当。明らかにO(1)解の存在が見える。チームの人に確認とったところ、自分の見てたO(1)解が嘘だったらしく、別のO(1)解を教えてもらった。早解きリレーなので、提出を押してそのままコーディング。コンパイルもせずに出したのでちゃんとコンパイル通ってくれるか不安だったけど、無事ACしてくれた。多分、コーディングしてた時間より、スリープからの復帰を待ってた時間とsubmissionsのページをリロードしてた時間のほうが長かった。

そのあとは特にやることもなく、「あれどんな問題なんです？」とか聞きながら他の人たちがコーディング進めていく様子を眺めていた。Color Gameが偶奇判定で解けるという証明を考えてるけど、まだ証明が完成してなくて辛い。k = 0で偶奇判定で解けるのは自明なので、kに関しての帰納法で証明できそうな気がしてる（気がするだけ）。早解きリレー。リレーが終わった後のほうが話題がたくさんあって、チームの人と仲良くなれそうな気がするのだけど、リレー終了後にそんなに時間なくてお話できなかった。つらい。

 

閉会式

チーム対抗リレーが終わり、そのまま閉会式へ。二日間の様子を収めた映像が流れる。楽しかったなーと思いながら眺めてた。indeed社からTシャツのプレゼントがあるという話があって、記念撮影したら解散だった。会場出口でtunenarazuさんとchako0407さんが待っていた。握手して帰宅するシステムらしい。確か、会場側から眺めて右側にtunenarazuさん、左側にchako0407さんが居た気がする。左側のほうから会場を出たので、chako0407さんとだけ握手して帰ることになるのかなーと思ってたら、tunenarazuさんが、「あ、逃げた」と言ったので「そういうシステムになってたのか」と思ってtunenarazuさんと握手して帰宅。tunenarazuさんごめんなさい。

 

帰り道

kyosさんとclimpetさんと会場出口で出会えたので、ここにDarseinさんともう一方が加わって空港へ。同じ大学の同期は別班で空港に行ったらしい。climpetさんが空港までのコストが最小になる経路を知っていたのでclimpetさんについていく。climpetさんとkyosさんはDarseinさんと知り合いなので、Darseinさんと接点無いのが私だけという状況。「JAG合宿のときは『あれがDさんかー』と遠目に見てました」という話をしたら「どうぞ気軽に、welcome!」みたいなことを言われた。

空港までの電車の中で、来年以降もCODE FESTIVALがあるのなら、大学の競プロサークルに入部してきた一年生が目指す一番最初の大会としていいですよねーという話になっていた。そこそこのレベルの競プロerが相当数存在することが確認できたので、来年本選に出れるかどうかかなり危ういと思っているので、プログラミング暦半年の人が目指すにはかなり高い目標な気もしたが、ICPC国内予選で1完するという目標よりはだいぶましらしい。とても充実したプロコンだったので来年は予選参加者が激増してさらにレベル上がりそうな気がしているのだが。。。

他にも、DさんからあさプロMidDの解法を教えてもらったり、kyos氏がじゃんけんの比較関数みたいな比較関数を使ってsortしたら停止性は保証されるのかとかそういう疑問を投げたりしてた。

空港に着くと、同じ大学の人々がほとんど同じ飛行機で帰るらしいということが分かった。久留米高専の某氏も（話しかけなかったけど）発見した。帰りの飛行機がポケモンジェットだった。飛行機の到着後、手荷物が最後の最後まで出てこないというちょっとしたトラブルに遭遇したが、ちゃんと手荷物見つかった。

空港から大学方面の自宅まで、climpetさんやj_gui0121さんと来年のICPCどうなりますかねーとかいう話をしながら帰宅してた。

 

おわりに

CODE FESTIVAL予選と本選、あさプロを通じて、競プロ欲が刺激されました。自分とおなじぐらいのレベルに100人以上居て、ここから頭一つ抜け出さなければと強く感じました。また、予選B・あさプロを通してAC数で差をつけられるように問題が調整されている場合に限って言えば、抜け出せるだけの実力になっているが分かり、自信につながりました。ARCとかSRMだと問題の難易度差が大きくてなかなか実力向上を実感できないんですよね。

CODE FESTIVALが終わり、なにやら寂しい気分に。いつまでもCODE FESTIVALの余韻に浸っていたい気もしますが、そろそろ次の大会（ICPCの2015年国内予選かな）に向けて練習をしなければ。

次の目標は
・TopCoder SRMでyellowになること。

・2015年のICPCでアジア大会に進出すること。（2チーム突破の壁を越えること）

・ARCで3完の壁を突破すること。

の三つでしょうか。院試に落ちない程度に、留年しない程度にがんばります。

CODE FESTIVAL 2014 こちらがお金を払わないといけないのではないかと思うほどにとても充実した大会でした。来年度もぜひ開催してほしいです。

リクルート社の皆様、運営サポーターの皆様、その他CODE FESTIVALの運営に携わられた皆様、ありがとうございました。