ACM 国際大学対抗プログラミングコンテスト アジア東京地区予選
http://www.teu.ac.jp/icpc/regional/results.html
優勝しました！
team combat
id:tanakh ことT氏とK氏と僕、高校時代の知り合いとコーチI氏によるチームです。
プログラミングコンテストとは？
ACM国際大学対抗プログラミングコンテストでは、コンテストの最初に複数の問題が出題され、いかに多くの問題に、いかに早く正解できるかを競います。
与えられる問題のジャンルはさまざまですが、どの問題も入力に対し正しい出力をあたえるプログラムを作る形式です。たとえば、「3点(0,0),(0,4),(3,4)をむすぶ3角形は直角三角形か？」ではなく、「3点が入力されたとき、それをむすぶ三角形は直角三角形かどうか求めるプログラムを作れ」という問題が出ます。選手の回答は審判プログラムによって判定されます。正解すると風船がもらえるのが特徴で、しかも試合の重要な戦略要素のひとつです。
このようなルールにもとづいて順位が決まります。つまり容易な問題を素早く判断して優先的に解くことが重要なので、つまり僕はただ問題読んでるだけじゃないよ！
本番
会場の後端の全体が見渡せる(これは重要)好い席が当たる。２つ前には去年の世界トップ上海交通大学Nimrod、同列最前には強豪复旦大学のPowderysnow TRY、右斜め前にはcombatの双対チームのechizenが着席します。Nimrodはすでに他の予選で優勝してオープン参加なのでいくぶん気が楽でした。
いつもどおり、T氏プログラム、K氏ペアプログラミング、僕問題解読の完全分業型フォーメーションで臨みました。
日本の問題セットは優良なので読みやすくて助かります。
| 時間(分) | 行動 | 風船 |
|---|---|---|
| 000 | コンテスト開始 | |
| 002 | 例年、問題セット先頭のA問題が一番簡単(これも優良ポイント)なのでAを読む。N<=10000までの自然数に対し、連続する素数列の和として表す方法の数を求める問題。単純に考えてO(N^2)乗の速度でも何とか間に合いそう。プログラミングチームに渡す。 | |
| 他の問題も読む。B問題が作業問題であること(作業の内容は長いので読まない)を把握。C〜E問題は挿絵があるので問題内容を推測。Fを読んだところ実数が出てくる。難しそうなので解読を折り返す。次に解くべきはC〜Eのいずれかだ。 | ||
| A問題を投稿、しかし４番目だった。のちにコンテスト中で最初のYesを出したのは同じ京大のechizenチームであると判明する。おめでとう。 | ||
| 010 | A問題Yes | ● |
| C問題。各面に色が塗られた立方体たちを、回転を許して同じ塗り方に変えるには、最低何面を塗り替えなければならないか。 | ● | |
| プログラミングチームがC問題の回転パターンを手動で生成するのにてこずっている間に上海交通大学が早くも２問目を正解するのを横目で見たので、E問題を解読。 | ● | |
| 038 | C問題Yes | ●● |
| E問題。重さが異なる何個かの石と長さ1の棒をつかって、部屋の天井から吊るすモビールを作りたい。最大どんな幅のモビールが作れるか。モビールの変数は全重量と支点からの左幅と右幅で、これに関して２つのモビールの合成算が定義できることを説明、プログラミングチームに渡す。 | ●● | |
| 067 | E問題Wrong Answer | ●● |
| E問題を書き直す２人を横目に会場を見渡す。複数の風船を獲得したチームが増えてくる。脅威でもあるが、簡単な問題の指針でもある。 | ●● | |
| 080 | E問題Yes | ●●● |
| B問題を説明する。ある図書館のロボット司書の行動をシミュレートする問題。あらかじめ訳を書き込んでおいた問題セットを渡す。こういう系の問題は長い問題文に書いてあることをそのとおりプログラムすれば誰でも正解できるので、確実に取らなくてはならない。 | ●●● | |
| B問題を解いている二人からの問題についての質問を受け付けながらのこりの問題解読を進める。最後のI問題まで読んで、I問題は難しすぎる捨て問題と判断。Fは探索と数値計算が必要のようだがそれにしては入力が大きすぎる。Gは問題設定はシンプルだが頭をひねる必要のあるおもしろい問題だ。Hはビンゴゲーム。 | ●●● | |
| 111 | B問題Yes | ●●●● |
| いったん3人で周りを見渡すとF問題の風船が多めに上がっている。僕が問題内容を説明。未来のレースカーにタイヤ交換のタイミングを指示し、最短時間でゴールさせる方法。T氏が問題サイズをみてこれはDPでは無いかという。実数のDPなんて聞いたことがあまりない。そう思って問題を見返すと確かに枢要な変数が整数になっている。DP解がひらめいたので二人に説明。K氏が7割、T氏が5割くらい分かってくれたのでもう3人でプログラムを書き始めることにする。 | ●●●● | |
| 問題を把握している僕が説明。T氏がプログラム。K氏がミスを拾ってゆく。 | ●●●● | |
| 138 | F問題Yes | ●●●●● |
| のこりの問題を全て説明し、作戦会議。D問題とH問題は並みのアルゴリズムでは遅すぎる。G問題は直感的には解けそうだが、きちんとしたアルゴリズムはなかなか見つからない。 | ●●●●● | |
| 170頃 | K氏がG問題に完全な解法を発見。T氏は懐疑的だったが、僕がその正当性を証明。G問題に取り掛かる。 | ●●●●● |
| 2人がG問題を作っている間に散らかった計算用紙を整理。D問題、H問題の解法が相次いで分かる。 | ●●●●● | |
| 東京大学のGNCチームが6問解いているのを見てT氏が心配しているので、こちらはあと3問解けるといって励ます。 | ●●●●● | |
| 210 | G問題Yes | ●●●●●● |
| D問題の説明は一言「両側から探索」 | ●●●●●● | |
| 246 | D問題Yes | ●●●●●●● |
| H問題の解法を説明。間に合いそうもないがI問題を解くよりはまし。のちに白い風船(H問題)を正解しているように見えていたチームのほとんどは薄れたピンクの風船(F問題)を挙げていたことがわかる。H問題に正解していたのは2チームだけだった。 | ●●●●●●● | |
| 295 | このままでは間に合わない。K氏が素早く書けるが不完全な解を出すプログラムを提案。 | ●●●●●●● |
| 299:55 | カウントダウンが始まってからH問題を提出。 | ●●●●●●● |
| 300 | コンテスト終了 | ●●●●●●● |
| H問題Wrong Answerやはりジャッジは甘くない。 | ●●●●●●● |
オープン参加のNimrodに1問差をつけられ、Powderysnow TRYに300分差をつけての東京大会優勝でした。
パーティーのときNimrodにH問題の解き方を聞きに行きました。十分な時間が余っていたためいろんな方法を試したそうで、最終的に鍵となる高速化を思いついたようでした。T氏の「強くなるためにどんな練習をしているんですか？」との質問には"Practice hard." "Practice every day."
練習会を開催したGNC、練習会に来た日本チーム、大会に参加していた全てのチームに。ありがとうございます。
