私が2年間競プロをして1理解した諸々の言語化を試みたものです。 異論反論は期待しています2。

コンテストの前、問題を解く前

準備は大切です。コンテストにでるなら、

  1. コンテストの日時を把握する
    • TopCoder部のカレンダーが便利
    • 登録が必要なものは忘れずする
    • どれに出ればいいか分からないなら、とりあえずatcoderとyukicoder上のコンテストに全部出るのがおすすめです
  2. 睡眠調整する
    • コンテストは深夜に開始することが多い
    • 眠いのを我慢して仕事しても全然効率的でない
  3. 紙とペンを用意する
    • 重要
    • ないとratingで言うと200,300ぐらいは下がる気がします
  4. ライブラリ等は用意しておく
  5. WA時のペナルティ等を確認しておく
    • 賞金等の条件もついでに

過去問を解く場合は、以下も確認しておくとよい。

  1. 解説はあるか
    • 解説がないと、解けなかった場合に経験値がほぼ得られない
  2. 入出力ケースや他人の提出は公開されているか
    • バグらせた時に楽

解く

まずは問題文を読んで理解する

重要な事項は紙に書き出そう

  1. 英語はそのうち慣れるので、我慢して読む
  2. 何を求めるのか理解する
  3. 入力の制約を確認する
    • 最大でどれくらいになるのか
    • 1-based ($1 \le x \le N$)か、0-based ($0 \le x \lt N$)か
    • $0$や$1$、$\emptyset$のようなコーナーケースは含まれるのか
    • loopや多重辺はあるか、sortされているか、等の勘違いしやすいところ
    • $\dots$
  4. 入出力の形式を確認する
  5. サンプルを把握する
    • 誤読に気付ける
    • ヒントになっていることは多々ある
    • ここでついでにテストケースを手元にファイルとして落としておく
  6. 違和感を感じる制約等はきっちりメモしておく
    • 大事

前処理

解法を探索する前に、とりあえずの前処理以下を行う。

  1. 問題を形式化する
    • 制約や求める対象を式の形などにする
    • ストーリーなどのどうでもいい情報を捨てて整理する
    • 考えやすくなる
  2. どれくらいの計算量なら間に合うか見積もる
    • 計算量が推測できれば、どのような形のアルゴリズムを使うかも推測できる
    • 制限時間が$1,2$秒で$10^8$ぐらいの操作回数ならだいたい間に合う3
    • 例えば:
      • $N \le 10^6$なら$O(N^2)$では通らなくて$O(N \log N)$未満が必要
      • $N \le 10^4$なら$O(N^2)$も通るが$O(N^3)$は無理
      • $N \le 25$とかなら$O(2^N)$が通りそう
    • $N \le 50$だから$O(2^N)$な方向で考えてたら実は$O(1)$でよかった、とかもあるので油断しないように
  3. 愚直解を考える
    • 明らかに間に合わないものでよい
    • 例:
      • 候補数が全体で$N$、ひとつあたりの判定に$N$だから、全体で$O(N^2)$かければ答えはでる
    • 考えないといけないのがどの部分か分かる

以上をして残った困難がその問題の核となる部分である。

方針を探索する

方針が立つまで、以下を繰り返す。 十分な回数繰り返し、変化がなくなった場合も終了する。

  • 貰える仮定は貰う
    • 入力をsortして問題ないなら、入力はsort済みであったことにする
    • 自明なケースを個別に処理できるなら、そのようなケースは入力されないものとする
    • クエリの列は、必ずしも順に実行する必要はない
    • $\dots$
  • 考えやすい形に直す
    • 見なれたもので言い換える
      • 最大値最小値
      • グラフ
      • 区間
      • クエリの列
      • $\dots$
    • なんらかの関係(遷移とか矢印とか順序とか)がみえたらだいたいグラフ
    • 式にする
  • 怪しい仮定の利用を試みる
    • 制約が妙に小さい
    • 大きすぎる制約があるとき、どのような方向は考える必要がないか
  • 何を求めれば何が求まるかを考える
    • あるものを求めるのに、何を求める必要がないか、も考える
    • 例:
      • 半分に分けた場合の結果のそれぞれが求まれば、全体が求まる
      • ひとつ前の場合の結果が分かれば、次も分かる
      • ある状態からの結果に、その状態へ辿り着くまでの仮定は関係しない
      • $\dots$
  • 有名なアルゴリズムを試す
  • 選択肢を列挙し、順に全部試す
    • 処理すべき対象の列があるとき、その処理の順に関して: 前から/後ろから/半々などで分けてから合成/畳み込んだ結果などから一気に
    • 再帰っぽいとき、何に関して再帰するか
      • 例えば区間なら: 右端/長さ/左端
      • 例えば木なら: 部分木の大きさ/部分木の高さ/辺や頂点の重み/$\dots$
    • $\dots$
  • 情報を整理する
    • 図を書く
    • 具体例を作る
    • 現在得られている仮定とそのゴールを書き出す

基本的に行なっているのは証明4の作製に近い5と思っています。

そもそも全てはしらみつぶしな探索だと思っています。 空中から解法を取り出しているような挙動をする人間はよく見られますが、諸々を(本人の意識にものぼらない程に)高速に実行しているだけであるはずです。

解けないと思ったら

なぜ解けないのか考える。その原因を大別すると、

  • 問題文の誤読
  • 知識の不足
  • 考察の不足

だろう。 よって、

  • 問題文の読み直し
  • (可能なら)仲間への相談
  • なぜ解けないのかの説明を試みる
  • (どうしても自力で解きたいなら)時間をおく

をする。

それでもだめなら諦めよう。

十分な時間(初心者であれば$30$分程度か)考えても分からないならその後数日考えても分からないだろう、ということはよく言われる。 復習は大事なので、諦めたら解説を見て実装して提出してACを貰うところまできっちりやっておくべきである。

方針が立ったと思ったら、確認

その方針で本当によいのかを確認する。 ICPCなどで仲間と相談ができるなら、一緒に確認するとよい。

  • 計算時間は間に合うか
  • (コンテストであれば)実装は間に合うか
    • ライブラリの有無
    • 得意不得意
  • なにか勘違いをしていないか
    • 非自明なケースをいくつか作って試す

また、ある方針でよいことが確認できても、追加の考察により実装量が減ることはある。 可能だからといってすぐに実装を開始しないようにしよう。 例えば、以下のようなことを考える。

  • 定数倍の計算時間を使って、丁寧に実装するのではなく全探索的にごまかせないか
    • 例えば、off by oneの丁寧な実装を、$-2 \dots +2$を全部試して最も良いものを選ぶことでごまかす
  • 似たような計算部分をまとめて処理できないか
    • 例えば、各数に$-1$を掛けるなどでいい感じにする
    • 例えば、事前にsortすることで場合分けを消す
  • $\dots$

実装する

決めた通り丁寧に書くだけ。 チームで解いていて、実装が重かったり計算機の台数に強い制限があるなら、ペアプロをしよう。

どう書けばいいかにつまるのなら、問題や解法に対する理解が足りていない可能性が高い。 ひとまずeditorを閉じて紙の上に戻ったほうがよいことは多い。 off by oneのあたりは実装しながら考えればよいと思うが、それでもあまり複雑になるようならこれも一度紙の上で整理するべきだろう。

この辺りに関しては以前似たようなことを書いたので参考にしてほしい: 競技プログラミングでコーディングの際気を付けていること - うさぎ小屋

実装した後

提出する前に、本当に解けているのか確認する。

  1. サンプルケースは全て試して確認する。
  2. サンプルケースに漏れがあるなら、追加で試す。
    • コーナーケース
    • 非自明なケース
      • 手で試した出力と合うことを見る
    • 最大ケース
      • 本当に間に合うのか確認する

このあたりのテストは自動化すべき。以下のようなツールも利用することができる。

その後に、提出する。

解けてなかった時

提出したがpretestなどで落ちてしまった時。

どう落ちたか確認する

その状況を元に原因にあたりをつける

  • Wrong AnswerなのかRuntime ErrorなのかTime Limit Exceededなのか
    • WAやTLEが多いなら解法が間違っているのかも
    • REは実装が間違っていることが多い
    • 手元では合っているものが落ちているなら初期化忘れ等の未定義動作が疑われる
  • (それが見れるのなら) どのくらいの数のケースが落ちているのか
    • 落ちているのが少ないならコーナーケースっぽい

また、コード中にassert (false);等を仕込んで提出し、Wrong AnswerなどがRuntime Errorに変わるか否かで追加の情報を得るテクがある。

撃墜ケースを探す

どのようなケースで落ちているのか考える。 複雑なケースで落ちているのでなければ、以下のいずれかで具体的に撃墜ケースが得られる。

  • 問題となりがちなケースをもう一度確認する
  • 非自明なケースを手で作ってみる
  • ランダムにテストケースを生成させ試す
    • 愚直解を書いてそれと突き合わせる

「プロコンでのWrong Answerの原因」ビンゴ // ichyo.jpあたりを眺めるのもよい。

解法/実装の修正

  • 根本的な部分で勘違いがあったなどしたとき
    • 考え直し
    • コンテストであれば別の問題へ移ることも考える
  • 修正できる問題の場合
    • 修正する
    • 実装を後から修正するのはとてもバグを埋めやすいので注意する

まとめ

基本は全探索を丁寧かついい感じにやるだけ。

真に新しいものを生み出せる人間なんてめったに存在しませんし、そこらのコンテストでそのような所業が要求されるはずがないです。 解法とは無から新しく生み出すものではなくて、過去の問題で見た解法を切り貼りして構成するものであるはずです。 「ひらめき6」だとかのような存在しないものを追い求めるのではなくて、積極的にパターン化を目指すべきだと思います。

競技プログラミングの問題の解き方、そのマニュアル

競技プログラミングの問題の解き方、そのマニュアル

  • Thu Jan 19 17:12:17 JST 2017
    • $6$つ目の注釈に関して、後から見直して言葉が強すぎるなあと思ったので少しマイルドにしました (元の文章はコメントアウトした)
    • ついでにテストツールへのlinkも増やしておいた
    • 他はそのまま

  1. 記述時現在、赤はまだまだ遠い程度の黄色coderです ↩

  2. この文章を書く動機のひとつはこれなので、特に競プロのプロ各位は是非よろしくお願いします ↩

  3. 記述時現在の話。昔はもっと厳しかったようですね ↩

  4. 「答案」ではないよ ↩

  5. なのでCoqなどの対話的定理証明支援系を一度触ってみると、何かが得られるかもしれないし、得られないかもしれない。 ↩

  6. どうやって発見したかをうまく言語化できないものをまとめて「ひらめき」と呼んでるだけで、意識できない位置で実際に行われているのは(何らかの効率化があるとしても基本的に)しらみつぶしな探索だろうと思っています ↩