これは競技プログラミングで失敗する事例紹介の記事です。華麗な解答も大事ですが、初めて解いたときに詰まった経験を蓄積することは良い教材になると思うので記事にした。
今回はプログラミングコンテストチャレンジブックの「気楽にウォーミングアップ」の部分和問題で詰まったときの思考の過程をたどってみる。
整数 a_1,...a_n の中から選んで和がちょうど K になる事が可能かどうが判定せよ。
1<=n<=20
-10^8<=a_i<=10^8
-10^8<=K<=10^8
思考の過程
Attack 1 : 愚直にいく
まずは地道に答えを出す方法を考えた。もし愚直なアルゴリズムで済むならそれが一番だから。
部分和のとり方は $a_i$ を使う or 使わないの選択を任意の $i$ で行うことで決まる。これは全部で $2^n$ 通りある。足し算は最大 $n$ 回なので、必要な計算回数はだいたい $n\times 2^n$ 回くらい。$n=20$だとこれヤバそうな感じなので、なにか工夫がいる？
Attack 2 : 削れる計算過程を探す
愚直にやると、枝分かれして指数的に増える状態ごとに足し算を計算するからヤバい。ならなんとかして葉の部分の計算を削減したいよな。こういうのって途中で出てくる状態が他のとこでも使えるんでしょう、どうせ。適当に例を考えてみるか・・・
このへんで詰まる。愚昧な私には何の計算が再利用されてるのかが見えない。
反省の過程
Review 1 : 答えを確認
答えを見ると Attack 1 の方針で深さ優先探索をしてるだけでした。
しかし $n$ の大きさが $n=50$ とかならこの方法は無理じゃんと思って調べると $n=50$ の場合でも、計算量 $O(nk)$ でいく方法がある。それを思いつけなかった時点で詰まったことに変わりない。で、どうやるのかといえば、任意の $l,m$ に対して
整数a_1,...a_lの中から選んで和がちょうどmになる事が可能なら True 不可能なら False
という問題 $(l,m)$ を考えると、３つの問題 $(l,m), (l-1,m), (l-1,m-a_{l})$ の間に漸化式が立つので $l,m$ を小さいものから順に書いていけば $l=n,m=k$ のときの答えが求まるという、動的計画法の典型だそうだ。
アルゴリズムは何にせよ、どこかで計算の削減してるわけで、今回一体どこに計算を削減する余地があったんだろうか。
Review 2 : 答えにたどり着けなかったのはなぜ？
節約された計算は結局何だったのか？
考えてわかったのが Attack 2 で節約しようとしたのは $a_i$ たちによって作られる部分和の値そのものの計算過程を、削減対象としていたためうまくいかなかった。今回問われていたのは、部分和が$K$になることが可能か不可能かだったので、削ろうと考えていた対象が間違っていたことに気づいた。だからいくらこの方向で攻めても答えが出ないわけだ。
教訓 : 計算を削減したい対象をよく考えよう
しばしば解決したい対象そのものを見誤ることがある。そうなると問題は解けない。落ち着いて自分が今何を解決しようとしてるのかメタ認知する事が大事。