※ この記事は 2024 年度の国内予選終了直後に書かれました
はじめに
私が参加できる全ての ICPC 国内予選が終了したので，ここでその攻略法についてまとめてみる．想定読者は来年以降の ICPC 国内予選に参加してアジア地区大会への出場権を勝ち取ろうとしている人である．
ICPC は現代の競プロのコンテストの中ではかなり尖ったルールをしており，最大のパフォーマンスを発揮するには事前準備もある程度必要である．しかしそれについて解説されることは少ないため，競プロの実力自体は十分ありそうなチームが力を出し切れないまま敗退している例をしばしば見かける．ここでは細かい点も含めて押さえておいた方が良い項目をいくつか紹介しようと思う．
本記事は 10 位以内で国内予選を通過しようとしている東大チームを想定して書かれたものである*1．他大チームの場合でも，参加する環境や通過ボーダーなどの違いはあるが概ね参考になる内容だと考えている．
またこれは私が 5 年間所属したチーム SPJ における戦略である．チームごとに得意分野は違うので，必ずしも真似る必要のない部分もこの記事には含まれている． なお，参考までにチームメンバーは私，nok0, zkou の 3 人である．3 人とも AtCoder のレートが 2600 前後である．
用語について
同点の順位付けの際に参照される「各問題に掛かった時間の合計」のことを消費時間，誤答の際に加算される 20 分間のことをペナルティと (ここでは) 書く*2．
2024 年度のルール
詳細については公式ページの競技ルールおよび成績判定ルールを参照のこと．ここでは特に重要な点について述べる．
- 問題数: 9 問
- 制限時間: 3 時間
- チーム人数: 3 人
- ライブラリ: 電子ファイルの持ち込み可
- インターネット: 予選システムへのアクセス以外使用不可
- 全問同配点
- 同点の場合，各問題に書けた時間の合計が小さい方が上位
- 誤答 1 回につきペナルティ 20 分
昨年度からの変更点
- 問題数増加 (8 問
9 問)
- ライブラリの持ち込み制限緩和．紙媒体以外のものも持ち込み可になった
- USB などの機器がコンテスト中に扱えるようになったわけではなく，必要なファイルはあらかじめ PC に移しておく必要がある
- 得点するための作業内容の変化
準備物
- PC
- キーボード
練習
- 実は国内予選のルールを練習できるセットは国内予選や模擬国内の過去問以外にほとんどない
- セットが足りなくなったら AOJ のバチャ機能で適当な難易度の 9 問を選んで 3h を走る
- 幾何や構文解析は現代ではさほど出題されないので，あまり特化しすぎないように
- ただしこれらのジャンルを苦手意識なく捌ける人員が 1 人はいた方が良い
- コーダー全員が同一のキーボードを使うので，それに合わせて練習をする必要がある．
- アジア地区では US キーボードなのでできるだけそれで練習すべき
リハーサル・模擬国内
- 用意したスクリプトなどが正常に動作するかを重点的に確認する
- 序盤でつまずかないことを意識する
コンテスト中の立ち回り
開始前
- スクリプトやソースファイル，ライブラリなどを準備する
- 現行ルールなら紙で用意しなくて良い
- 画面の右半分にエディタ，左半分にブラウザを開いておく
開始直後
- 印刷を待っている間はできることがかなり制限される
- ギリギリまで最適化するなら以下の手順で処理する (FA 狙い*3でなければここまで急がなくてもいい)．
- おおまかには，A を読んで解く人 (人 1)，その間に B を読む人 (人 2)，印刷の受け取り待ちの人 (人 3) に分担する
- はじめ，人 2 が PC の前に座り，人 1 がその左側に控えておく
- 人 1 が A を読んでいる間に人 2 が A のサンプルをコピペし，入力を受け取るコードを書く
- A を読み終わったら人 2 が PC の右側によけて，人 1 が PC 前に座って A を書き始める．
- A を書いている間に人 2 がマウスでブラウザ画面をスクロールして B を読む or A の制約を読んでオーバーフローやコーナーケースなどを確認する
- A を提出する
序盤
国内予選は序盤が命
よってまずは前半の低難易度をペナなく速やかに終わらせることが重要
- 練習としてはやはり過去問をやるのが有効
- グリッドグラフ上の探索が頻出
速さは重要だが無理して最高速度を出す必要はない．ペナルティ 20 分の罪は非常に重いため慎重さも非常に重要
- 多少遅くとも堅実にペナなしで行くのが最強．焦った他のチームが勝手に沈んでいく
- 問題を解く人数の目安は AB で各 1 人，C で 1-2 人，DE で各 2 人，F 以降は状況次第という感じ
- 問題を読んだ人がすぐ解けたからと 1 人で特攻して実装で沼にはまるパターンもよくある
- D くらいからは解けたと思っても解法をいったん別の人にちゃんと伝えたほうが良い．計算量や実装方針についても慎重に確認する．1 台しかない PC は貴重な資源．見切り発車で実装を始めない
- 場合によっては実装も 2 人でやる (ペアコーディング)．1 人が書いている間に細かい点をもう 1 人が精査する．序盤の有利を取るために人員を割く価値はある
- デバッグもそうだが，チームメイトのコードをスムーズに読むのには慣れが必要．少なくとも使用しているテンプレートくらいは事前に把握しておく
- 実装途中で補助者が抜けることは可能だが，逆に実装の途中で補助に加わることは難しい
- よって半分以上の場合で実装を 2 人で始めることになる
- 遅い戦略のようだが，少なくとも今の環境ならこれくらいじっくりやっても序盤でリードが取れる．本番でミスなく序盤を乗り切るのは意外と難しく，価値のあること
- 強いチームはこんなことしなくても楽勝なんだろうけど，そういうチームはこんな記事読む必要がない
- 問題を読んだ人がすぐ解けたからと 1 人で特攻して実装で沼にはまるパターンもよくある
- 3 問以上を並列でやるのは最序盤だけでいいくらい (一番伝えたいこと)
- 10 位に入れば良いことを考えると，むやみに散らばるのは事故率を上げるだけ
- 「3 人がそれぞれ D, E, F を読んで考察していた」みたいな参加記をよく見かけるが，これをやっていいのはうちより強いチームだけだと思う．難易度順が分かっているセットなので，人員を分散させるメリットが薄い
- 考察が終わって実装を待っているときでも，変数名や更新式などの実装の細部を詰めたり，ペアコーディングをしたりと，次の問題に行くより先にやるべきことは大抵ある
中終盤
- 多くの問題を通すことが必要な非常に苦しい状況でない限り，基本的に考察は 2 人以上でやる
- 実装も多くの場合で 2 人以上でやる
- 残り 80 分くらいの段階からは 3 人で 1 問に集中することも考え始める
- ときには問題を捨てて他の問題の話を聞きに行く判断も必要
デバッグ
- 3 時間は短いので，そもそもデバッグ自体が弱い行動．ペアコーディングでできるだけ回避したい
- 1 人でやらない & やらせない
- 解法を実装者だけが把握している場合でも，必ず他の人が応援に行って解法と実装内容を確認する
- 他者の視点からの方がコードの欠陥に気付きやすいため
- コードを印刷して計算機を別の問題のために空けるという手法がある
- バグのあるコードを計算機を使ってデバッグするか，新しく解法が思いついた問題を書くかは難しい判断
- 事前に ICPC Japan Problems *5などで実装が重めの問題を利用して実装時間を見積もる練習を行うのが良い．実装時間は大きな判断材料になる
- 実装が爆発したときは方針ごと変えることも考える
- この場合でも他の人と要相談
テクニック集
コマンドなど
- あらかじめスクリプトを書いておくことで，よく行う操作をターミナル上の短いコマンドで済ませる
- コマンドの使い方に関してドキュメントを書いておく
- 少なくともコーダー全員に共有する必要があるため
- 次の年に使う頃には忘却しているため
- ファイルの生成などについては，このルールであれば事前にやっておけばよい
データセットファイルの扱い
- ダウンロードをする際のブラウザの設定が「保存するフォルダを毎回選択する」となっているならば，それを「国内予選本番で作業するディレクトリに保存する」に変更する
手元実行であることを生かす
- 実行制限時間は提出やダウンロードにかかる時間を除いても 5 分程度はあるとみなせる
- 手元の計算機はどのくらいの処理に何秒かかるかを競技前に確認しておく
- スタックサイズを拡張しておく
ulimit -s unlimited
- オンラインジャッジと違い，手元のデータセットの実行途中に実行時エラーになってもペナルティにならない
- print デバッグのときには標準出力ではなく標準エラー出力を使う．消さなくて良い
- 提出前に目視で出力を確認する．高々 10 回くらいしか出さないんだからサボらずにやったほうが良い
- 出力の量が多すぎ/少なすぎないか？
- 出力の値でおかしいものはないか？
- (例) 非負整数が答なのに大きいマイナスの値がある
- (例) 非負整数が答なのに大きいマイナスの値がある
- WA になった場合，古い出力ファイルを上書きせず保存しておく
- コードの修正により出力結果に差分が生まれたことを確認してから投げ直す
東大チームの出場環境
- 2024 年度は東大から出場したチームはほぼ全チームが浅野キャンパス (本郷キャンパスのすぐ横) にある情報教育棟の Mac を用いて出場していた
- 10 チーム以上に印刷システムを提供しつつ監督を行う関係上こうなっている
- この環境は来年度以降も変化しないものと思われる
- 環境に不満があれば別の教員に個人的に依頼して別の場所で監督員をやってもらうしかない
- この場合，プリンタやモニタなどを含めた環境も自分たちで用意する必要がある
東大情報教育棟の Mac
- 普段の環境とかなり違うと思うので，一度は情報教育棟で想定通りの動きができるか確かめた方が良い
- 駒場の情報教育棟にも同じ端末がある
- 管理者権限によってソフトウェア等のインストールが制限されている
- キーボード
- デフォルトで日本語配列
- USB 接続の自前のキーボードを接続できる
- ルール上，コンテスト中に使えるキーボードは 1 台のみであることに注意
- プリンタ
- 位置が遠い
- 印刷の際には端末にログインしている ECCS アカウントのパスワードを求められる
- パスワードはアカウント所持者しか知り得ないため，毎回同じ人が取りに行くことになり不便．当日だけパスワードを変更してチームメイトに共有する手はあるが，パスワードの変更はすぐには反映されないこと，およびセキュリティ的によろしくない行為であることに注意してやりましょう
- 実行速度
さすがに 5 回も国内予選をやっていると色々知見が溜まるものですね．普段考えていたことを文章化するとこんなにも長文になるのかとびっくりしました．他にもこんな Tips あるよっていう方はコメントで教えてください．適宜更新していこうと思います．
近年はアジア地区に行く強い東大チームが少なくなってきていると感じています．実力のある後輩たちが少しでも通過やすくなってくれると良いなと思って書きました．これから国内予選に挑む方のお役に立てれば幸いです．アジア地区横浜大会編もまたいずれ書きます．
