【競技プログラミング】ナイーブな解法を考えてからDPに機械的に変形するテクニック

この記事は、AtCoderで水色になりたい人向けです。緑色になりたい人でも読んでおいて損はないレベルだと思います。

動的計画法（DP）という言葉をおれは競技プログラミングで初めて知りました。メモ化は知っていたのですが、DPは知りませんでした。

おれは電気系出身です。ナップザック問題は知っていましたが、授業で解いたかどうかはわかりません。少なくとも、コーディングした記憶はないです。今なら、AOJなどを使って実際に問題を解く演習が出されたりするのでしょうか。そうすることには意味があると思います。

このようにDPは競プロ入門者にとってなかなかの鬼門なのですが、水色になろうとすると、DPはそれなりに出てきます。

そこで今回は、「ナイーブな解法からDPに変形する」という視点でテクニックを紹介します。おそらくそれがもっとも、初級者がDPに立ち向かう上で大切なことだからです。

まずはナイーブな解法を考える

DPの問題には、「時間が無限にあったら解けるのになぁ」と思うものがあります。「未来のコンピュータなら解ける」とも言います。

全列挙してしまってそれぞれをチェックすれば答えにたどり着くことは出来るという場合です。しかし大抵の場合、それでは正答出来ないように出来ています。なぜならば、そんなに簡単では問題にならないからです。

しかし、この「ナイーブな解法をまず考えてみる」というのは解法探索の上では意外に有力で、そこを突破口にしてテクニックを適用するというハメパターンに持っていくことが出来ます。

もちろん、テクニックを適用したあとにも考察をしないといけない場合もありますが、まずは、ナイーブに考えてテクニックを適用して解法探索の範囲を狭めるということは大切です。

なぜ、ナイーブな解法では間に合わないのに、 DPに帰着させると解けるのか。それは、問題を解くことにフォーカスして、余計な情報を計算させていないからです。例えば、全列挙の場合であれば、何かしらの評価値の最小を探すと言ってるのに、それぞれの順序を全部知ることは無駄ということになります。（全列挙がわかることは、最小値が見つけられることの十分条件でしかないということです）

テクニック

「ナップザック型」: 指数オーダーはナップザック型と思え

DPというとまず嵌るのはナップザック問題です。

これはN個の品物（価値vi,価格pi）があった時に、自分の所持金で買える最大の価値和を求めよというものなので、 DPの典型問題です。

全2のN乗通り（買う買わないをN回）を求めてしまい、それらについて価格が所持金以下か？をチェックするというナイーブな解法が考えられますが、大抵の場合はN=10万程度と大きい制約があり、それでは解くことが出来ません。おもむろに計算してみると、2の10万乗というのは、10進数で3万桁くらいだそうです。終わる頃には宇宙がなくなってそうです。アルゴリズムがあれば、それが一瞬で求まるのだから不思議ですね。

ナップザック型の基本問題を紹介します。

Knapsack 1：モロにナップザック問題です。
Vacation：おれは夏休み問題と呼んでいます。似たような問題は良く出て、 LeetCodeでも出題されています。各点で前の状態に依存した選択が可能なことが特徴です。この「前の状態を覚えておく」というのはDPで典型的な手法です。

「TSP型」: 階乗オーダーはビット探索と思え

巡回セールスマン問題（TSP）は、グラフの全頂点を一度ずつ回って帰ってくるパスの最小コスト和を求める問題です。

これもナイーブな解法を考えてみると、頂点を通る順番としてN!を考えて、それらが実現可能かチェックしていくという解法が考えられますが、通常、うまく行きません。超初級の問題では、N=8程度程度だったりして、ナイーブ解法でも間に合うということがありますが、大抵はN=10とか20とかです。こうなると途端に間に合わなくなります。階乗というのがいかに恐ろしいかがわかります。

この場合にどう考えればよいかというと、基本的な考え方は「順序を覚えるのをやめて、集合で考える」ということです。

こうすることで順序（階乗）を集合（ビットマスク。指数）に落とすことが出来ます。

TSPでは順序を覚えるのをやめて「今までに辿った頂点集合」と「最後に到達した頂点」を状態として、最適値を求めていきます。あとの計算では、最後に到達した頂点より前にどう通ったかというのは興味がないことを利用した手法といえます。

巡回セールスマン問題：モロヘイヤです。
Swap and Flip：難易度は高いですが、基本的な考えはTSPです。というか解説動画の中でりんごさんが階乗オーダーのナイーブ解法を示したあとにいきなりビット探索の解法に「さも自明であるかのように」進んでいることから、彼が頭の中でなんらかの定型的なテクニックを適用したのではないかと思い、この記事を書こうと思いました。
Keyboard Purchase：これも難易度高めですが、基本的な考え方は同じです。すでに使ったアルファベット集合と使ってないアルファベット集合との間だけで遷移に必要な計算が出来るという点がポイントでした。

計算量をヒントにして解法を探索する

上のテクニックの根本にあるのは、「ナイーブにやったら間に合わないのだから良い方法があるのだろう」という予想（ないしは期待）です。競技プログラミングが想定解法のある問題である以上は、このアプローチは正しいです。

その他にも、競技プログラミングの問題は基本的に、ナイーブにやったら解けないけど、うまくやると解けるという場合が多いです。例えば、Nが10万で、ナイーブに考えると2乗アルゴリズムだが、きっとNlogNのアルゴリズムが存在するのだろうとか。その場合、二分探索とかセグメント木のようなものを使うのではないだろうかとか。あるいは、はじめにソート分を払ってしまうと何かうまい方法が見つかるのではないだろうかとか。

Nが10とか20程度ならばビットDP（Nが少し大きければ半分全列挙とか）を疑いますし、整数の範囲が10の9乗まで行ってる場合は、二分探索とか座標圧縮を疑います。その他にも問題の背景が64ビット整数のXORであればきっと桁DPだろうとか、 N=300程度のグラフ問題ならワーシャルフロイドかといったような特殊な疑い方もあります。

このアプローチを実践してる人は多いと思いますし、反則ではないので実践するとよいと思います。

glhf