なぜｄｐ「やるだけ」なのか ～動的計画法について考える その１～
これは、Competitive Programming Advent Calendar 2016の17日目の記事です。
競技プログラミング（以下，競プロ）においてよく出題される動的計画法（Dynamic programming，通称dp）について，「dpやるだけ」という表現を稀に見かけます．競プロを始めた人のうち，多くの人が（少なくとも自分にとっては）最初の壁のうちの一つと言ってもいいdpというジャンルがなぜ「やるだけ」などというパワーワードを伴ってしまうのか．今回はそういうところから，ふわっと動的計画法について考えてみようと思います．どちらかといえばテクニック的な内容というよりは自分がdpの問題に触れるときに意識しているようなことを書いているだけなので，参考になったりならなかったりすると思いますがご容赦のほど．
動的計画法とは
wikipedia によると「対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。」ということです．文面だけ見ると難しそうです．とてもやるだけという感じはしません．
そう思いながらもう少しwikipediaの記事を読み進めていくと，例題としてフィボナッチ数列が出てきます．
// A_0 = 1, A_1 = 1 のフィボナッチ数列 A_n の n番目の値を返す関数 int Fib (int n){ if ( n == 0 ) return 1; if ( n == 1 ) return 1; return Fib (n - 1) + Fib (n - 2); } /* オーバーフローするから 実用コードでゎない */
多分，動的計画法を調べてここにたどり着いた人のうち少なからずの人が「いや，こんな書き方するかなぁ」って思うのではないかと思います．確かに関数がメモ化してあれば無駄な呼び出しはなくなるかもしれないけど，別にだからと言ってあまりうれしさも無いような印象を受けるのではないでしょうか？そもそも関数で書くかなぁ（完全に私見）
実際，自分がネット漁りしながら勉強していた時はそんな風に思った記憶があって，普通に行列累乗する方法でええやんと思ってました．あるいはwikipediaにも記載のあるような，
// A_0 = 1, A_1 = 1 のフィボナッチ数列 A_n の結果を result[n] に格納する int result[1000]; result[0] = 1; result[1] = 1; for(int i = 2; i < 1000; i++){ result[i] = result[i - 1] + result[i - 2]; } /* オーバーフローするから 実用コードでゎない */
という素直なコードを書いて「わざわざ再帰とか使わないよなぁ」とか思っていたと思います．
さて，メモ化するとか配列で書くということが上の動的計画法のページではクローズアップされていますが，今回の趣旨の上ではそれはそれほど大切ではありません．ただ，このフィボナッチ数列の例にも「dpやるだけ」なのかの兆候はみてとれます．
冒頭から極論ですが，「dpやるだけ」の裏付けは以下の２つのどちらかではないかと思います．
- case 1：（相対的に）実装する段階で解の正当性の考察が完了している．
- case 2：マイクパフォーマンス
元も子もない2つを上げてしまいました．
case 2 については「ハラスメント，ダメ，絶対」の精神でもう各自の裁量に任せるしかないのですが，case 1については少し考察の余地があります．上のコードの例はある意味ではcase 1 で，定義に従って計算しているだけなのですが，それは取りも直さず正当性の考察が完了していると言えます．だって定義に従って計算しているだけだもの（2回言う）．
こういう部分をもうちょっと考えることで，動的計画法の習得の一助になるようなことを考えていきたいというのが本稿の趣旨です．与太話感がパないですが，それぞれのレベルで感じることを書くのもアドベントカレンダー記事っぽくてよいかと開き直ります．なにより「dpやるだけ」と（口に出さないまでも）感じられるようになるというのは，そこまで悪いことだとは思わないので，その瞬間を得るための考え方の指標とかを示すのを目標に．
今そこにある動的計画法 ~Clear and present dp~
こんな問題を考えてみましょう．
- サイズ N の intの配列 A[N] が与えられる．
- 与えられた配列の中身のうち，最大値を求めよ．
制約 1 ≤ A[i] ≤ 100000, 1 ≤ A[i] ≤ 100000000 ( 0 ≤ i < N )
素直にコードを書くとこんな感じのコードになるのではないでしょうか．
// 要素数 N の配列 A の最大値を求めて返す int MaximumOfArray (int A[], int N) { int max = -99999999; // Aのどの数字より必ず小さい数値で初期化 for(int i = 0; i < N; i++){ if(A[i] > max) { max = A[i]; } } return max; }
ね，簡単でしょう？これならやるだけと言ってしまう気持ちもわかる（？）
冒頭で「動的計画法は難しそう」と書きましたが，これは立派な動的計画法です．
どう考えるのがいいのかというのがありますが，wikipediaの定義を満たすかという観点で言えば
- point 1 :「対象となる問題を複数の部分問題に分割」
- point 2 :「部分問題の計算結果を記録しながら解いていく」
この2点を確かに満たしています．
- point 1 について：ループを順次回している部分に着目すると，「\( 0 \)から\( N - 1 \)までみる」という問題を「\( 0 \) から \( i \) （ \( i ≤ N-1 \) ）までみる」という問題に分解している．
- point 2 について：\(0\)から\(i-1\)までみた計算結果が 変数 max に入っているのを，\(i\)番目のループで利用している．
ここで最も「動的計画法」だなぁと思う点は，max という変数が移り変わっていくところです．移り変わっていくといっても，ランダムに変わっていくわけではありません．そこには純然たるルールがあります．例えばループが\(i\)で止まった時にmaxに入っている値は何かと聞かれれば，それは明確に決まっています（今回の場合，「\( 0 \) から \( i -1\)までみた最大値」です）．逆に言えば，あるルールで情報を伝えていった先に答えが見つかる，そのようなルールを決めている，といえます．
情報を余さず届かせる
同じような例ですが，見方を変えて以下のような問いを考えてみます．
あなたはすっごいものぐさな40人の生徒からなる学級の担任の先生です．さて，今日あなたは先日採点したばかりのテストを皆に返却しました．
ところが，うっかりもののあなたは，クラスの最高点を調べておくのを忘れてしまいました．
そこで，生徒たちから得点を聞きたいのですが，生徒は皆，「点数は覚えてるけど，テスト用紙はもうカバンにしまってしまって出すのがめんどくさい，てゆーか先生のところまで行くのもめんどくさい」と非協力的です．
一方，あなたも負けず劣らずものぐさのため，一人ひとりの机に赴いて点数を訊くなどということはする気がありません．
そこで，教壇からふんぞり返って「わかった，じゃあ今から私が指名するから，指名された人は前後左右隣の人に点数を訊いて，それと自分の点数を比べて一番高い点数だけ覚えておいてくれたらいいわ」と宣言しました．
【問題】どのように指名していけば，最終的にクラスの最高点が教壇から動かなくてもわかるか，その順番を答えてください．
最終的に図中の21番太郎君に訊いて答えを知りたいとして，どういう順番に聞いていけばいいかという問題．
まぁ答えはいくつもあります．例えばこんな感じでしょうか？
見た目はまぁまぁ一見全然違いますが，どちらの回答でも最終的に21番太郎君に訊くとクラスの最高点を知ることができるでしょう．
さて，ここで少し自問してみて欲しいのですが，指名された生徒の一人一人は前後左右の生徒と自分の点数を比べて（時には自分の点数すら忘れて）その中で一番大きい数字を覚えるようにしているだけです．それを何らかのルールに則って順番に実行させることで，あなたはクラス全体の最高点を知ることができています．さらに言えば，解答例１の薄緑の線を省略しても大丈夫そうと考えることもできるかもしれません．しかし大切なことは，生徒たちに許された動作を考慮したときにどう順番に実行すれば，余さず必要な情報を手元に届けられるか，ということです．今回の問題の場合，クラスの誰が最高得点を得ているか分からないので，全員を経由していることと，それが最終的に21番太郎君の所まで運ばれてくること，です．極端なやり方を挙げれば，1から40までの順に機械的に指名するというのを40回繰り返してから21番太郎君に訊くのでもいい．
" 何"を，" どう" 伝えるか!? ~「状態」と「遷移」 ~
本記事のテーマが「なぜdpは「やるだけ」なのか」という事だったので，いかにも簡単すぎる題材を選んでみたのですが，競プロにおける多くのdpの問題はこのような" 何"を，" どう" 伝えるかという部分を考察することを必要とします．この”何”にあたる部分を「状態」，"どう"にあたる部分を「遷移」と呼びます．（上の例だと，40人の脳内に何の数字があるかという情報が「状態」，{前後左右に訊いて最大値を覚える}と{それを実施する順番}が「遷移」にあたります）
dpの問題はこの「状態」と「遷移」をペアで適切に決める問題と言えます．もちろん，問題によって状態や遷移が自明に決まっているものもあります．例えば最初のフィボナッチ数列の例は，値が状態にあたり，漸化式が遷移にあたる上，疑問の余地なく定義されているので，自明と言ってもいいかもしれません．ただ，多くのdpの問題は両方を決めることを要求されます．またこの２つは独立にそれぞれ決められるわけではなく，最終的に得たい情報を得るためにペアで上手くいくように適切に決めてやらなければなりません．
おそらく一般的には「状態」を適切に設定することが難しいです．「遷移」は自分の行動にあたるので，（効率的かはともかく）何かを挙げることは可能なのだけれど，遷移ドリブンで考えると適切に状態を定義できなかったり広くなりすぎたりしてしまいます．かといって必要な情報は網羅していないといけない．逆に言えば，適切に状態を設定できるということに正しく遷移させられるという要求が含まれます． 上の40人学級の例で，どう遷移を選ぶかという問題に対して割といろいろ考えたり工夫することができるのも，すでに状態が設定できているからとも言える．
ようやく冒頭のcase.1について述べることができます．
- （相対的に）実装する段階で解の正当性の考察が完了している．
どんな問題も，解の正当性の考察が完了していれば，そりゃあとはやるだけでしょと言えるでしょう．それがなぜdpで（相対的に）顕著なのかという点を考えると，dpで解ける問題は，上のように「状態」と「遷移」の2つを決める必要がある．2つも決めないといけないのだからほかの問題に比べると分からなければ手の付けようがないのだけれど，逆にその2つ，とりわけ「状態」を適切に決められた時には遷移も混みで考察出来ているため，いうなれば解のダブルチェックが出来ている状態です．なので安心感があり，実際dpの問題は提出できればACできることが多い気もします．
(個人的には，正しく推移できているかというチェックは数学的帰納法のプロセスそのものなので，解きながら証明も進んでいくお得感があると感じることさえあります．逆にdpがある程度解けるようになると今度は貪欲法が難しいと感じるようになるケースは，遷移ドリブンで考えてしまっているケースが多いのではと思ってます)
そして更に，上に書いたようにdpの難しさは「状態」の設定にあるので，いいかえれば場面場面に応じたテクニカルな「状態」の設定方法が先人の知恵，典型的なアルゴリズムとしていろいろ名前がついています．テクニカルなので，最初は思いつかなくて当然です．しかしテクニックなので，一度習得してしまえば応用が利き，かつ遷移後の状態が求めるものかどうかがすぐに分かるようになります．（ちなみに私が最初に感銘を受けた状態設定をもつdpはナップサック問題でした．そのあたり次章で書きたいと思います）．なので，見知ったdpの問題に帰着できた場合にも，実績あるアルゴリズムだからというよりは，「どう推移するかが頭の中で完全に把握できる→正当性が保証される」が引き金となって，ああやるだけだなぁと思ってしまうのではないでしょうか．
ということで，この記事の結論としては敢えて，
dpは「状態」と「遷移」を正しく決められれば，正当性が保証されるので，やるだけ
としたいと思います．出来るとは言ってないしこれトートロジーですよね
なので，dpがイマイチ得意でない人や例題は分かるんだけどという人は，状態と遷移を意識して考察してみると幸せになれるかもです．（私がそうだったという話）
そうはいっても漠然としているので，状態と遷移について続いて記事を書く予定です．
アドベントカレンダーも終盤戦に差し掛かってきました．明日はroiti46さん（CPACその１）とcamypaperさん（CPACその２）です．楽しみですね！
