2012-07-16

VK Cup 2012 Finals

13 日より，サンクトペテルブルグで開催されていた VKCup の決勝に参加していました．

VKCup はヨーロッパの SNS の会社である VK が今年から始めたプログラミングコンテストです．Codeforces 上で行われていて，今年は上位 50 人が決勝に招待されました．2009 年以降，TopCoder Open や Google Code Jam が決勝進出人数を 25 人程度に縮小しているのに対し，50 人は近年の大会としては随分と多く素晴らしいです．もしかしたら，ロシアで開催なので，進出者が非常に多いロシア人の飛行機代を浮かせることができていて，人数の割にお金がかかっていないのもあるかもしれません．VK は毎年やりたいと言っているらしいです．しかし，年齢制限が今年と同じだと，僕はもう出られない…

僕は C 問題で詰まってしまい，その後も奮わず，残念ながらあまり良い成績を残せませんでした．しかし，VK は豪勢にも参加者全員に副賞のノート PC をくれました．やったー．

2012-07-09

ターゲット昇格＆ TopCoder Open 2012 決勝進出

2007 年に TopCoder に参加し始めてからほぼ 5 年，ついにレーティングが 3000 を超え，ターゲットになることができました．念願の目標達成で，めちゃくちゃ嬉しい！！！

レーティングが 2200 以上になると，名前の表示が赤色になり「レッドコーダー」と呼ばれるようになります．これは上位を目指す TopCoder 参加者の一つの大きな目標です．現在世界に 300 人弱居て，参加者の上位約 3% になるらしいです．さらに，レーティングが 3000 以上になると，名前の左側のインジケータが満タンになり，射的のマトのようになるので「ターゲット」と呼ばれます．これは現在世界に 18 人なので，(全体の上位約 3% の) レッドコーダーのさらに上位約 6% ということになります．

僕が最初にレッドコーダーになったのは始めて 1 年も経たない 2008 年上旬のことでした．もっとも，その頃は TCO インフレのおかげでぐっと上がっただけで，すぐに黄色に戻ってしまいましたが，その後またじわじわ上げていき，始めて約 2 年の頃に 2900 代に乗せることができました．その頃は，そのままターゲットになれるかなと割と思っていました．しかし，その考えは完全に甘く，2900 代の境界をうろちょろしたり，2010 年には 2993 (!!!) まで行ったにもかかわらず，3000 に乗せることができませんでした．（2900 代の壁というのは実は結構有名 (?) で，僕だけでなく多くの人が苦しんでいます．）

その後，忙しかったことやモチベーションが落ちていたこともあり，レーティングをずいぶん下げ，2700 前後や，一時期は 2300 前後を彷徨っていました．2993 まで行ったにもかかわらず，僕はこのままターゲットにならないで終わってしまうんじゃないかと，内心本当に思っていました．しかし，ICPC 世界大会に向けた練習で調子が上がっていたことや，TCO 等で運の良いラウンドが続いたことにも助けられ，本当にやっと，レーティングを 3000 代に乗せることができました．

ずっと赤色上位に居たので，しばしば (元) ターゲットと勘違いされて，申し訳ない気持ちになったりしていましたが，今日からそうならなくて済むと思うとかなり気が楽です．とはいえ，僕の実力で，ターゲットを保つのは簡単じゃなさそうです…ひぃ…

あと，今年も TopCoder Open (TCO) のアルゴリズム部門でオンライン予選を勝ち抜くことができました．今年は苦しい戦いでしたが，かなり運がよかったです．10 月頭にフロリダです．楽しみ！

去年はアルゴリズム部門に俺を含んで 4 人の日本人ファイナリストが居ましたが，今年は俺と岩田だけになりました．かわりに，マラソン部門は 5 人（岩田含むけど）も進出しているので，今年も日本人がいっぱい居て楽しそう．

2012-06-12

プログラミングコンテストでの乱択アルゴリズム

DeNA 主催の TopCoder メンバー交流イベント "TopCoder Meetup in Japan" で「プログラミングコンテストでの乱択アルゴリズム」というタイトルで話をさせてもらいました．

プログラミングコンテストでの乱択アルゴリズム

View more presentations from iwiwi

乱択アルゴリズムは，プログラミングコンテストで頻出のトピックとは少なくとも今は言いがたいですが，今年の Google Code Jam で急に 2 問も出題されたことを中心に，ちょくちょく出始めています．少し体系的に議論できるぐらいには問題がたまってきたかなというのと，もしかしたら更に流行るこれからに備えることができるかなということで，乱択アルゴリズムを題材に選びました．

イベントではそのほか，DeNA の会社紹介，立食スタイルの交流会，副島さん (=rng_58) への 100 の質問コーナーなど，色々あり充実していて，とても楽しかったです．

TopCoder Meetup in Japan : ATND

2012-05-19

銅メダル獲得: 2012 ACM-ICPC 世界大会

ワルシャワで行われていた ACM-ICPC の世界大会にて，11 位を獲得し，銅メダルを受賞しました．日本チームのメダル獲得は 2003 年より 9 年ぶりになります．日本初の，3 人全員がレッドコーダーのチーム．日本で応援してくださった皆様の期待に応えメダルを獲得することが出来，良かったです．

OB/OG 会の皆様をはじめとし今まで指導してくださった皆様，特に世界大会で苦い思いをしそこでの反省を教えてくださった先輩方 (特に岩田)，本当に今までお世話になりました．我々のメンバーが以前のチーム達より単純に優れていたというわけでは決してなく，知見の蓄積によるコミュニティ全体としての成長の結果だと思います．（あと運）

メダルを獲得でき，皆様におめでとうと言ってもらえ，本当に嬉しいですが，一方で我々としては，これは納得の行かない結果でもあります．事前の過去問を用いた練習では，スコアが金メダル圏内から出ることは殆どなく，本気で金メダルを狙っていました．実際，序盤は本当に金メダル圏内に長らくつけていて，アドレナリンどばどばでしたが，後半で失速してしまい，2 問も書いたコードが受理されないまま終わってしまいました．本当に悔しい．コンテストが終わった後のチームは，完全にお通夜ムードでした．

我々は，5 年間，同じチームで ICPC に参加していました．少しずつ戦い方が変化してきて，最初の年と今を比べてみると，戦い方が全然違う．個人の能力の成長もありますが，それだけではなく，チームとして本当に成長し，チームで戦うということはどういう事がようやく分かってきたのだと思います．最初のうちは，「3 人いるのに PC 1 台しかないなんてふざけてるな」と思っていましたが，今では，それを活用できるようになり楽しめるようになりました．非常に面白い体験ができたなあと思います．

年齢制限により，ICPC はもう引退です．先輩たちがしてくれたように，我々も，上記の点のような得られた知見を次の世代に伝える等，日本チームを応援していきたいと思います．まずは近いうちに自分の意見や反省をまとめたエントリを書きたいところです．

追記: 書きました http://topcoder.g.hatena.ne.jp/iwiwi/20120608/1339162885

2012-03-28

プログラミングコンテストでのデータ構造 2

情報オリンピックの春合宿で「プログラミングコンテストでのデータ構造 2」というタイトルで講義をさせてもらいました．スライドは以下になります．

プログラミングコンテストでのデータ構造 2　〜平衡二分探索木編〜

View more presentations from Takuya Akiba

プログラミングコンテストでのデータ構造 2　〜動的木編〜

View more presentations from Takuya Akiba

平衡二分探索木の話と動的木の話をしました．アルゴリズム的な説明だけでなく，実際にコードにする際に楽に実装するためのポイントにも重きをおいています．実装に関する話は，アルゴリズム系の講義資料等にはあまり書かれることが無いため，珍しい資料になっているかと思います．（そもそもとして動的木の話は珍しいですが…）

「プログラミングコンテストでの」というタイトルになっていますが，平衡二分探索木・動的木が本当に必要になる問題は少々稀で，プログラミングコンテストに関する話としてはかなり進んだ話になっています．一方，プログラミングコンテストに限らず，それらを実装したいと思っている人には少なからず役立つと思います．

タイトルの末尾に「2」がついているのは，同タイトルの講義を一度やっているからです．その時は，Union-Find 木，セグメント木，バケット法の話をしました．その時の資料も公開していますので，よければご覧下さい．