考察問題

概要

プログラミングをする前に、問題をいろいろ分析しなければならない場合がある。
愚直にプログラミングしようとするだけで難問だったり、高速化が難しかったりすることも多い。
そんなとき、手を動かす前に頭を動かしてみると、実は簡単な問題だったという場合が多い。
（問題全体としては、考察後に実装が重い場合もある）

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

ここでは、ある程度パターンに分けて、考察の例を紹介する。
もちろん、これ以外のパターンもいくらでも存在する。

考察方法の例

必要十分条件を利用する

問題の条件を、同等かつより単純なものに言い換える。

例えば、$10$ 万桁ある整数が偶数か奇数か判定する問題。
「偶数である必要十分条件は、末尾 $1$ 桁が偶数であること」である。
つまり、その $10$ 万桁を文字列で持っていれば、末尾の文字チェックだけで済ますことができる。
$10$ 万桁ある数を $2$ で割ってみるより圧倒的に高速になる。

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

実は値が変わらない何か、増加はしても減少しない何かに注目する。

例えば、$3$ つの箱の中に $N$ 個のボールが入っていて、箱から箱へボールを移動することができる問題。
どれだけ移動しても、$3$ つの箱の中にあるボールの合計数は変わらない。
ということは、全状態の表現に $O(N^3)$ の三次元配列を用意しなくても、$O(N^2)$ の二次元配列で足りる。

例えば、数列に対して「先頭から順に値を足していき、初めて合計が $K$ 以上になる場所を探す」問題を考える。
各要素が $0$ 以上であれば、先頭からの合計は増えることはあっても減ることはない。
そのため、一度 $K$ 以上になった後は、それより右でも必ず $K$ 以上である。
この単調性を利用すると、前から愚直に調べなくても答えを高速に探せる可能性がある。

同じ内容の操作を何度も繰り返す話で登場しがち。

貪欲法を利用する

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

アルゴリズム系では、その決めつけの正当性を慎重に確認して実行する。

例えば、「この店の商品を $5$ 種類買って、代金を $10000$ 円以上にできるか？」という問題。
これに対し、「値段が高い方から $5$ つ買うことに決めつけて解こう」と考えることができる。

この例の場合、他の買い方を調査する必要がないことが厳密に証明できる。
雑な思い付きで実装に移ってしまいがちだが、実際には証明のスケッチくらいは持ってから実行すること。
そうしないと、ただの思い込みだった場合に実装時間を丸ごと無駄にすることになる。
残り時間が少ないなら、ワンチャン狙いで実装して提出してみるのも手であるが。
詳しくは「貪欲法」の記事参照。

ヒューリスティック系では、その決めつけの正当性はそこまで厳密に確認しない。

例えば、「この店の商品を $5$ 種類買って、代金をなるべく $10000$ 円に近づける買い方は？」という問題。
これに対し、「安い商品が多いから、高い方から $3$ つは絶対に買うことにしよう」と考えることができる。
つまり、残り $2$ つの全探索にして高速化しようということである。

この場合、他の買い方でもっといい解がある可能性が高い。
とはいえこの決めつけでもそんなに悪い解にはならないでしょう、という感覚的な根拠で実行される。
とんでもないことになることは少ないが、代わりに何を決めつけるかのセンスが要求される。
詳しくは「貪欲法（AHC）」の記事参照。

実験をする

例えば、「$2$ を $n$ 回掛けたときの $1$ の位はいくつか？」という問題があったとする。

$n$ が $6$ 桁くらいまでであれば forループで回せばいい。
しかし、$10$ 万桁くらいだととてもじゃないが実行時間が足りない。

そこで、小さい $n$ について実験してみると、次のようになる。

$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 \to 4 \to 8 \to 6 \to 2$ で、周期 $4$ でループしていることがわかる。
つまり、どんなに $n$ が大きくても、それを $4$ で割った余りさえわかれば答えは一瞬である。

そして、$4$ で割った余りは下 $2$ 桁を $4$ で割った余りと一致することも用いると、全体が一瞬で終わる。

このように、小さい $n$ について愚直に解を求めて一覧にすると、簡単な別ルートが見つかることがある。

対称性を考える

$2$ つの情報を入れ替えても問題が実質変わらない場合、それらをまとめて扱うことで楽ができる。

例えば、「$X$ は $A$ と $B$ の間の数か？」という問題を考える。
$3$ つの数があるため、これらの間の大小関係はいろいろなパターンが考えられる。
ここで、もし $A$ と $B$ が対等な関係、つまり入れ替えても話が変わらなかったとしよう。
その場合、最初に「$A$ が $B$ より大きかったらそれらを交換」とすれば、$A < B$ である前提で考えてよい。
このとき、「$A < X < B$ であるか？」だけ確認すればよくなる。

この例では愚直にやっても計算量やコードの複雑さはたかが知れているため、効果は薄い。
しかし、もっと高度になると、$A < B$ である前提が加わることでさらに深く考察できる場合もある。

最終状態から逆算する

実際に与えられた状況の終わりの状態から逆再生で考える。

ゲーム問題で、決着した状態からスタートして、決着が近い状態から順に調査していくなど。
詳しくは「バックトレース」の記事参照。

注意点

思いつきだけで実装しない

考察問題では、よさそうな性質を見つけると、そのまま実装に移りたくなることがある。
しかし、その性質が本当に全ての入力で成り立つとは限らない。

証明とまではいかなくても、なぜそれでよいのかの理由を確認してから実装すること。

コーナーケースに注意

一般的に使える理論を考えようとするので、特殊な現象が起こるケースへの考慮が抜け落ちがち。

例えば、ある値が最大の場合、最小の場合、何かと一致する場合、0 の場合など。
また、ある数値群が全部同じ場合、大小極端な場合、空の場合など。

考察から実装に移る前に、こういったものでも理論が破綻しないかも併せて確認すること。