ICPC のチーム戦略について
この記事は Competitive Programming Advent Calendar 2015 - Adventar の1日目の記事です。
はじめに
私 (JAPLJ) は今年の 5 月にモロッコで開催された ACM-ICPC の世界大会で（世界大会出場は 2 回までのルールにより）現役選手を引退となったので、ICPC についてなにかを書いておこうと思いました。
ICPC といえば特筆すべきルールはやはり 3 人で 1 台の PC を使うチーム戦というところで、これまでにも様々なチーム戦略に関する記事が書かれています：
- ICPCに向けたUECodersの戦略 - とどの日記
- ~shiokawaのICPCに向けたチーム練習、コンテスト直前の準備について - しおしおたのブログ
- ICPC のチーム体制について - (iwi) ｛ 反省します - TopCoder部
（少し探して見つけたものと覚えていたものを順不同に挙げただけなので他にも探せばあるかもしれません）
そういうわけでチーム戦略についての記事を書こうと思いますが、一般的な話をしても仕方がない（というより iwi さんの記事がたいへん役に立ちます）ので、自分の経験に基づいたチーム戦の話をしたいと思います。つまり、特殊な例についての記録ということになるので、これがそのまま他のチームの戦略に役立つことはあまりなさそうですが、一部でも参考になれば幸いです。
対象
この記事で対象になるチームは以下の条件を満たしているようなチームです。
- チームメンバーにりんごさん (rng_58) がいる。
おっと、りんごさんも既に現役選手を引退となったので、対象チームがなくなってしまいました。ここまで読んで頂いてありがとうございました。明日の記事は 1_000_000_007 さんで「悪問の具体的事例とどうすればその問題をよりよくできるか」です。楽しみですね。
というわけにもいかないので、粛々と続きを書きます。
チーム構成
ここからは基本的にモロッコへ行った際のチームをもとにします。
- rng_58 (りんごさん)
チームの司令塔です。問題の概要をいち早く把握し、迅速に解法を導き、それら解法の複雑さや現在の順位表をもとにどの問題から手をつけるべきかを判断し、適切なコーダーに仕事を割り振ります。
- semiexp (準急)
コーダー 1 です。圧倒的なデータ構造力とタイピング速度、自身も TopCoder の target である強みを活かして、序盤の簡単な問題・データ構造を活用する問題・複雑な DP の問題などを担当することが多くありました。
- japlj
コーダー 2 です。TopCoder のレーティング等では上 2 人に遠く及ばないところがあるので、その分を練習量でカバーし、幾何・探索・複雑な実装を要する問題を多く担当しました。
チーム戦略
とにかく、実際のコンテストでどういう戦略をとるかについて書きます。
開始時
計算用紙を 1 枚使って、現状の記録を行います。10問のコンテスト (A問題からJ問題まで) の場合は、まず大きく A から J までのアルファベットを紙に書きます。
コンテスト中は、問題の簡単な分野や内容を表す語句、既に担当コーダーが決まった場合はその名前 (うちの場合は s か j)、解き終えた場合にはそのアルファベットに大きく丸を書いていきます。この問題はどういう解法で時間がかかる、この問題をまずやって次はこれ、などといった相談はこの紙を使って行います。
最序盤
ICPC において最序盤の問題選択は非常に重要です。最初の 1 問を解くまでに余計な時間を 5 分かけてしまうと、その後解く全ての問題に +5 分ぶんのペナルティがかかることになってしまい、これは無視できない量です。特に World Finals のように問題の並び順と難易度に関係がない場合、簡単な問題を迅速に探しだす必要があります。
タイピング速度のある準急にテンプレートの準備などを行ってもらっている間、急いで問題文を読んでいきます。ここでは明らかに幾何のような図がある問題や問題文が長すぎる問題は一旦放っておいて、短くて単純そうなものを直感的に選んで読んでいきます（この辺の選択は経験がモノを言う場面でもあります）。準急が一通りの準備を終えた段階で、簡単な問題を渡すことができればベストです。
また、りんごさんは問題文の短いもの、数学の要素が強そうなものを優先して読みます。数学の問題は解法は難しくとも実装が容易であることが少なくなく、またりんごさんは数学の問題が非常に得意なので最序盤にこういった問題を通すことも多くありました。
序盤
開幕が落ち着いたら、序盤の比較的容易な問題を片付ける作業に入ります。ここをいかに滞り無く行えるかがかなり大切です。
この段階では、基本的に semiexp, japlj のどちらか片方が PC 前で実装を行い、もう片方がまだ読めてない問題文を読んで概要（とすぐに分かれば解法）をりんごさんに伝えていきます。りんごさんは自分で読んだり受け取ったりした問題概要から、次にどの問題をやるべきかを判断します。このあたりではまだ問題が比較的容易なためコーダーがどちらでも大差なく、また効率の観点からいっても同じコーダーが連続しないようにします。
あまりに簡単な問題という場合を除いて、りんごさんが問題を担当コーダーに任せるときには「何分ぐらいかかりそうですか？」という質問をします。これに正確に答えるのは非常に難しいですが、5 分や 10 分ぐらいの単位で大まかな値を申告します。解法がわかっている複数の問題のうちどれを優先して解くかを考えるときに、同じコーダーが連続しないことに加え、この申告時間の短い方を優先することになります。（この申告が間違っていることももちろん往々にしてありますが、申告より短く終わった場合はそれでよし、申告より長くかかった場合はその時点で戦略を考えなおして交代するなりの処置をとります）
中盤
だいたい全問題の概要がわかり、容易な問題が片付いたあたりです。コンテストの難易度にもよりますが、この時点で開始から 1〜2 時間程度、解いた問題数が 5〜6 問であることが多かったと思います。
このあたりに来ると、コンテスト終了時の順位表の推測が行えます。「この問題はまずどこのチームも解かない」「上位の間ではこれを解けるかどうかが重要になる」といったことから、「あとはこの 4 問にこういう順で挑戦して時間内に全て解ければベストで、5 位以内には入れる」のようにコンテスト終了までの大まかな見通しを立てます。
semiexp, japlj はそれぞれ担当する（わりと重めの）問題があってそれに取り組むという状態になっています。りんごさんは、難しい数学の問題があってそれに取りかかっているという状態になると良いですが、問題セットによってはこの時点ですでに暇になっている（残った問題はとても解けるものではない or コーダーが考えるべきことしか残っていない）ことも多くなります。
終盤
コンテストの残りが 1〜2 時間ほどになってくると、WA が出てしまってとれないといった問題も出てきます（中盤までにこういう問題を出すとかなりまずい）。このときデバッグに印刷は積極的に行いますが、コーダー交代は比較的慎重に行います。printf デバッグ等明らかに PC を使ったほうがデバッグが捗ること、コーダーの交代は頻発するとそれによる時間のロスも無視できなくなってくることが理由です。
手元で WA が出るケースを探して、見つけたら printf デバッグ等の結果も含めて全部を印刷し、それについて吟味している間はコーダーを交代する、といったケースが多かったように思います。手元でどうしたも WA になるケースが見つからずどうしようもない（もはやソースとにらめっこするしかなく、PC を使うメリットがない）と判断した場合もコーダーを交代します。
コンテスト後
コンテストが終わったあとは反省会を行います。
まず全問題を振り返って、それぞれについて吟味します。このとき、コーダーはもう一方のコーダーが担当した問題を（概要も含めて）全く知らない状態が良いです。これはりんごさんの采配と、その後のコーダーによる実装が詰まらず上手くいったということを意味しているためです。逆にバグが出て詰まってしまい印刷などをした場合、デバッグに協力するためにもう一方のコーダーにも問題概要と解法が伝えられる、といったことが起きてしまいます。
また、全問題のアルファベットを大きく書いた紙を使って全体の流れを確認します。解く問題の選択ミスはなかったか、順番は正しかったかの確認や、実装に申告より長い時間がかかってしまった問題についての検討などを行います。
練習について
個人練習
このチームの戦略は、それぞれの人がどういった能力を発揮するかが分かりやすくなっています。たとえばりんごさんは 5 時間の間、PC には全く触れません。一方僕や準急はふつうのコンテストと比べ、問題の解法を考える時間というのが圧倒的に少なく、ひたすらコーディングに偏った時間を過ごすことになります。
そのため個人としての練習もわかりやすく、たとえば僕は AOJ-ICPC の問題を全て（当時）埋めるなどの練習をしていました。
チーム練習
このチームの戦略はやはり明快で、コンテスト中の各人の動きはかなり分かりやすくなっています。そのためチーム練習に特別に時間を割くことはほとんどありませんでした（JAG の開催する模擬大会に出る程度）。
しかしモロッコに行ったときだけはチーム練習を行いました。序盤の戦略で「容易な問題をいかに滞り無く片付けられるかが重要」と言いましたが、りんごさんの分析により「序盤で詰まったコンテストでは最終的な成績も悪く、序盤がスムーズにいった場合最終的な成績もよい」ことがわかったためです（これはあくまでもこのチームの話です）。
確かに、これまでに調子の良かったコンテストを振り返ると、序盤の容易な問題を片付けた段階で 2 位に 2, 3 完の差をつけて 1 位ということが少なくありませんでした。一方、調子の悪かったコンテストでは、序盤にそこまで他チームをぶっちぎることが出来ていなかったように思われます。
そこで、モロッコにて「5時間コンテストの最初の1時間だけ練習」を行いました。これはその名の通り、5時間コンテストの過去問をひとつ選んできてそれで練習をするのですが、開始1時間が経った時点で終了とします。もちろん、戦略としては 5 時間コンテストに挑むつもりで行います。
つまり、直前になって 5 時間フルで使って難しい問題に取り組んだところで、いまからそういった実力を底上げするのには無理がある。だったら、コンテストに重要な序盤の動きだけを集中的に鍛えればよいし、そういった立ち回りなら直前からでも改善できる、という発想です。5 時間の練習で得られる成果を 1 時間で得ようという最高の練習です。効率 5 倍、スゴイ！
