内容別リスト/数学系/考察問題 - 競技プログラミング用 知識集積所

---

雑な説明

プログラミングをする前にいろいろ考察しなければならない場合がある。
極端な場合、そちらがメインで実装は数行だけ、という場合もある。

レベル

ABCのD問題以降でよく見るが、A問題からでも出るときは出る。
ARCやAGCは考察問題の割合がかなり多くなる。
プログラミングの能力はあまり関係なく、数学の実力が要求される。
（問題全体としては、考察後に実装が重い場合もある）

内容

愚直にプログラミングしようとするだけで難問だったり、高速化が難しかったりすることも多い。
そんなとき、手を動かす前に頭を動かしてみると、実は簡単な問題だったという場合が多い。
ここでは、ある程度パターンにわけて、考察の例を紹介する。
もちろん、これ以外のパターンもいくらでも存在する。

必要十分条件を利用する

問題の条件を同等かつより単純なものに言い換える。
例えば、10万桁ある整数が偶数か奇数か判定する問題に対して、「偶数である必要十分条件※は、末尾一桁が偶数であること」と考えて、そのチェックだけで済ますことができる。
詳細は必要十分条件※参照。

不変量や単調性を利用する

実は値が変わらない何かに注目する。
例えば、「3つの箱の中にボールが入っていて、どれかの箱から別の箱へボールを移動することができる」という場合、「3つの箱のボール数合計は変わらない」と考えることができる。
同じ内容の操作を何度も繰り返す話で登場しがち。
詳細は不変量※参照。

貪欲法を利用する

解答の一部をこちらで決めつけてしまうことで、問題を単純化する方法。
アルゴリズム系コンテストとヒューリスティクス系コンテストで少し扱いが異なる。

アルゴリズム系では、その決めつけの正当性を慎重に確認して実行する。
例えば、「この店の商品を5種類買って、代金を10000円以上にできるか？」という問題に対し、「値段が高い方から5つ買うことに決めつけて解こう」と考えることができる。
この例の場合、他の買い方を調査する必要がないことが厳密に証明できる。
雑な思い付きで実装に移ってしまいがちだが、実際には証明のスケッチくらいは持ってから実行しないと、とんでもないことになる。
残り時間が少ないとかならワンチャン狙いで実装して提出してみるのも手であるが。
詳細は貪欲法（アルゴリズム系）※参照。

ヒューリスティック系では、その決めつけの正当性はそこまで厳密に確認しない。
例えば、「この店の商品を5種類買って、代金をなるべく10000円に近づける買い方は？」という問題に対し、「安い商品が多いから、高い方から3つは絶対に買うことにして残り2つを全探索※しよう」と考えることができる。
この場合、他の買い方でもっといい解があるかもしれないが、この決めつけでもそんなに悪い解にはならないでしょう、という感覚的な根拠で実行される。
とんでもないことになることは少ないが、代わりに何を決めつけるかのセンスが要求される。
詳細は貪欲法（ヒューリスティック系）※参照。

実験をする

例えば、「2をn回掛けたときの1の位はいくつか？」という問題があったとする。
nが6桁くらいまでであればforループで回せばいいとして、10万桁くらいだととてもじゃないが実行時間が足りない。
そこで、小さい2について実験してみると、

nの値	2^n	答え
1	2	2
2	4	4
3	8	8
4	16	6
5	32	2
6	64	4
7	128	8
8	256	6
9	512	2
10	1024	4
11	2048	8
12	4096	6
13	8192	2

となっていて、2→4→8→6→2で周期4でループしていることがわかる。
つまり、どんなにnが大きくてもそれを4で割った余りさえわかれば答えは一瞬である。
（そして、4で割った余りは下2桁を4で割った余りと一致することも用いると、全体が一瞬で終わる）

このように、小さいnについて愚直な方法で解を求めて一覧にしてみると、大きなnに対しても使える簡単な別ルートがみつかることがよくある。
雑な思い付きで実装に移ってしまいがちだが、実際には証明のスケッチくらいは持ってから実行しないと、とんでもないことになる。
残り時間が少ないとかならワンチャン狙いで実装して提出してみるのも手であるが。

対称性を考える

2つの情報を入れ替えても問題が実質変わらない場合、それらをまとめて扱うことで楽ができる。
例えば、「XはAとBの間の数か？」という問題。
いろいろな大小関係が考えられるが、もしAとBが対等な関係（つまり入れ替えても話が変わらない）なら、最初に「AがBより大きかったらそれらを交換」とすればA<Bである前提で考えてよく、「A<X<Bであるか？」だけ確認すればよくなる。
この例では愚直にやってもたかが知れているが、もっと高度になるとA<Bである前提が加わることでさらなる考察を進められるような場合もある。

最終状態から逆算する

実際に与えられた状況の終わりの状態から逆再生で考える。
例えば、「1に対して、3倍した後で1を足すか引く、という操作を繰り返して指定の数を作れるか？」という問題。
1から初めて作れる可能性がある数を列挙していくと爆発するが、指定の数を作るには1回前が何であればよいかを考えると簡単である。
詳細はバックトレース参照。

注意点

コーナーケース※に注意

一般的に使える理論を考えようとするので、特殊な現象が起こるケースへの考慮が抜け落ちがち。
ある値が、最大の場合、最小の場合、何かと一致する場合、0の場合、など。
ある数値群が、全部同じ場合、大小極端な場合、空の場合、など。
考察から実装に移る前に、こういったものでも理論が破綻しないかも併せて確認すること。

関連内容

必要十分条件※

考察方法の一種。

不変量※

考察方法の一種。

貪欲法（アルゴリズム系）※

考察方法の一種。

貪欲法（ヒューリスティック系）※

考察方法の一種。

バックトレース

考察方法の一種。