torus711 のアレ

主に競技プログラミングの問題について書きます

CODE FESTIVAL 2014 参加記

 CODE FESTIVAL 2014 が大変素晴らしかったので参加記を残そうと思います。

1 日目

本戦前

 秋葉原の風景をキョロキョロ眺めたり、スマホの地図アプリ見まくったりしながら、田舎者丸出しな感じで会場へ向かいました。受付後、参加賞の T シャツの受け取りとか交通費清算とか色々すませて本戦会場へ。

本戦

 6 問正答のパーカーを目標に設定して、いざ本戦に臨みました。多少手こずりつつも*1、1 時間程度で A から E の 5 問を AC して、「これはパーカー行けるっしょ」みたいな気持ちになっていました。 が……駄目っ……! F から急に解けなくなって、比較的解けそうだった F, H も最後まで通せず、結局後半 2 時間は「座ってるだけ」になってしまいました。

トークライブ - アルゴリズムのイメージを擬人化する

 @chokudai さんによるトークライブ、「アルゴリズムのイメージを擬人化する」を聞きました。擬人化の意義とか、割とまともなことを言っているようでやっぱり色々ぶっ飛んでいて面白かったです。題材のアルゴリズムは Brute Force, DFS, BFS, ビームサーチの 4 つでした。ビームサーチ、割と参加者層の広いこういうところでサラっと出てくるほどメジャーな存在っぽくなっていてちょっとびびる。話の大筋はぶっ飛んでいましたが、各アルゴリズムについて要所はきっちり抑えて解説されていたので、アルゴリズム(特にビームサーチ)を知らなかった人にはちゃんと勉強になりそうな感じでした。

パフォーマンス - 生ニコ生放送

 @nico_shindannin さんと @iwiwi さんによるペアプログラミングを見ました。問題は 2011 TopCoder Open, Algorithm Championship Round, Level 1 : PerfectlyFairGame でした。
 まず比較的ナイーブな解法を考えてから、問題の特徴を活かして計算量を削減していくという流れで、視聴者もついて行きやすい構成になっていました。また、段階的に問題を解いていく過程はわたし好みで良かったです。考察及びコーディング中に入る @iwiwi さんのツッコミが的確かつトーク的に面白くてとても楽しめました。
 最終的に枠内できっちり AC して締めていて格好良かったです。

ライトニングトーク 01

 @not_522 さんによる「幾何問題の美しい解き方」及び @tsunenarazu さんによる肉 LT を聞きました。(順番どっちだっけ……)
 肉の印象が強すぎてちょっとアレ。国産とかは当てにならない・肉の等級は数字で見る・目の下はツラミ。
 幾何は『コンピュータ・ジオメトリ』読めば強くなれそう。

エキシビションマッチ

 1 日目の最後はエキシビションマッチの観戦をしました。トップ層のコーディングを見れる機会はほとんど無いのでこれは外せない。
 開始直後に問題に目を通してからじっくり観戦をすることにして、まずは Reading Phase 。時間短いし解法ぐらい見えるかと思っていたけどそんなことは無かった。けれども @semiexp さんがきっちり二完していて流石でした。
 コンテスタントがときどき変なことをしていて面白かったです。

2 日目

 何故か寝付けなくて 2 時間程度しか寝ていない状態で参加することになってしまったのでレッドブル(ボトル)を買ってから会場へ。0 日目の夜も 2 時間程度しか眠れなくて 2 日間で 4 時間しか寝ていません。遠足前の小学生みたいな。

あさプロ

 asa!
 どんなに眠かろうとプロコンがあれば出なければ、ということで前述のレッドブルをお供に参加。30 分程度で A を AC して、「もう 1 問ぐらいは行けそうだなー」という気持ちになっていました。が……駄目っ……!( 2 回目) B の Greedy (だったはず)は分からず、C は行列累乗で通そうとして誤差の前に爆死という有り様で、結局 1 時間ほど「座ってるだけ」をしていました。本戦と合わせて合計 3 時間も「座ってるだけ」になったのはちょっと辛かったです。

トークライブ - プロコン高速化対策

 @colun さんによるトークライブ、「プロコン高速化対策」を聞きました。普段はあまり考えていなかった「ヒープは遅い」問題に関して、具体的なソリューションを与えてくれたので、高速化が必要になったら是非活用したいと思います。デフォルトコンストラクタの呼び出しも消さないといけないのは割と盲点だったので、聞けてよかったです。ちょっと考えれば当たり前ですけども……。
 後半の除算の高速化は全然原理が分からなくてやばさを感じていました。パズルゲームのシミュレータの高速化はいつか使えそうなので覚えておこうと思います。

A.I. Challenge 決勝戦

 予選の感じから、多分通ってるだろうということでトークライブや LT ではなくこっちに参加することに決めてから、結果発表を待っていました。予想通り通っていたので、安心して会場へ。
 実を言うと、締め切り一週間前ぐらいに急に参加したくなってコードを書き始めたという感じだったので、予選で上位にいたときからかなりびびっていました。わたしは(勉強も兼ねて)モンテカルロ木探索を適用しただけというコードで、ゲーム固有の知識は殆ど使っていないので、実況や周囲の戦略談義について行くのが大変でした。
 本戦は残念ながら準決勝で敗退してしまいましたが、あまり得意なジャンルというわけでもないので、予選を通過できただけでも上出来かなと思います。しかも、後から公開された予選のランキングによれば 4 位の Rating だったようなので満足しています。

チーム対抗早解きリレー

 戦犯になりそうでかなり前から恐怖していたのですが、まさかの @semiexp さん*2と同じチームにアサインされていて更に「はわわー」となっていました。実際にはそんなにやばい問題は多くなくて、適切に担当者を決めればさほどやばくない感じの問題セットでした。あと @semiexp さん普通にいい人でした。
 本戦順位の低い方から A, B, C... と割り当てられ、わたしは G 問題を担当しました。どう見ても普通のナップサック問題で、逆に不安になってチームメイトに確認を取ったりしつつ、順番が回ってくるのを待っていました。コーディングスペースが空いてから 5 分程度で AC できたのでまぁ良かったかなと思います。一度言語選択を忘れて CE を出してちょっと焦りましたが。競技中はかなりテンションが上がっていて、AC 確認してからかなり大げさにガッツポーズをしてしまいました。立ち上がるより素早く AC を伝えられるので合理的な判断だったと思います。

閉会式

 各種表彰が行われました。音ゲーとタイピングゲームにまで表彰が行われていて面白かったです。

まとめ

 とても楽しいイベントでした。加えて、交通費・宿泊費を始めかなりの好待遇でやばかったです。運営スタッフさま、ありがとうございました。
 もし来年も開催されるなら、是非参加したいと思います。
 小学生の作文みたいな記事になってしまいましたが、この記事をもって運営スタッフさまへの感謝の意を表したいと思います。(なんとかかっこよく締めようとする努力)

*1: D ( パスカルの三角形 ) に 20 分も使ったのめっちゃ悔しい……

*2:本戦・エキシビション・あさプロ Hard 優勝