ARC073-F「Many Moves」とインラインDP

Pocket

「うーん、オーダーが落ちないなあ……」

「先輩、競プロですか?」

「うん。最近、妹に競プロを勧めて、DPを教えてるんだけどさ」

「えっ、先輩、妹さんいるんですか!?」

「そこから? 妹が一人いる2人兄妹だよ」

「へ~。先輩の妹さんかぁ。会ってみたいなぁ。かわいいですか?」

「なんでそんなに興味津々なの。別に普通だよ」

「そんなことより、この問題だよ」

「これは、ARC073-F『Many Moves』ですか。確かにDPですね」

「うん。DPを教えてるから、自分ももっと勉強しないといけないなぁと思うんだけど、難しくて」

「なるほど…… えーっと、O(NQ)の解法は分かります?」

「そうそう、そこまでは分かるんだよ。

$$dp[q][i][j] = q 回動かした後に駒が i, j にある状態への最小コスト$$

としたいところだけど、片方は必ず、直前の移動先である x[q-1] にあるから、添字の j を減らせるんだよね」

「そうですね。

$$dp[q][i] = q回動かした後に、駒が x[q-1] と i にある状態への最小コスト$$

ですね。ちなみに、初期状態は駒が A と B にあるので、x[0]=A としてしまって、入力の x を 1-indexed にして、

$$dp[q][i] = q回動かした後に、駒が x[q] と i にある状態への最小コスト$$

とすると良いですよ」

「そうすると、初期状態では、もう一方の駒が B の位置にあるから、 dp[0][B] = 0 になるのかな。その他の dp[0][i] は ∞ でいいか」

「この場合、更新式はどうなりますか?」

「駒が x[q] と i にある状態に移動させることを考える。前の段階で駒が x[q-1] と j にあるとすると、目的を達成するためには、 x[q-1] = i か j = i が成立する必要がある。

x[q-1] ≠ i のときは、駒が x[q-1] と i にある状態から、x[q-1] の駒を x[q] に動かすから、コストは |x[q-1] – x[q]| 必要だね。

$$dp[q][i] = dp[q-1][i] + \bigl|x[q-1] – x[q]\bigr|\tag{1}$$

だ。一方、x[q-1] = i のときは、x[q-1] と j にある状態から j の駒を x[q] に動かすから、コストが |j – x[q]| になって、j は好きに選べるから、最小になる j を選べばいいんだね。

$$dp[q][i] = \min_j\left(dp[q-1][j] + \bigl|j – x[q]\bigr|\right)\tag{2}$$

だね」

「この計算量はいくらですか?」

「ある q について、dp[q][*] 全体の計算量を考えると、dp[q][x[q-1]] 以外では、式(1)の更新式になるから、O(1)。これが N-1 個あるから O(N) だね。また、dp[q][x[q]] は、式(2)の更新式になって、j が 1 から N まで(0からN-1まで)ループするから、O(N) だね。この和だから、O(N) だ。クエリは Q 回あるから、全体で O(NQ) だね」

「ですね。計算量を落とすには、“式(1)をしたくない” という気持ちと “式(2)を高速化したい” という気持ちが必要ですよね?」

「うん。どっちも O(N) になってるからね」

「まず、式(1)を見てみましょう。

$$dp[q][i] = dp[q-1][i] + \bigl|x[q-1] – x[q]\bigr|\tag{1}$$

この |x[q-1] – x[q]| は、i によらない定数ですよね」

「そうだね。ってことは、“全体に足す値” を管理すれば、実際には足さなくてもいいのかな?」

「そうですね。全体に定数を足すことを省略しても、式(2)の最小値の位置には影響しません」

「ああ、そこも考えて省略できるか考えないといけないんだね」

「実際に定数を足すのは dp[q][x[q-1]] 以外ですけど、そこは計算後に定数を引き算すれば大丈夫です」

「じゃあ、式(2)はどうするの? セグメント木の気配を感じるけど、各要素に異なる値を足してから最小値を取るから、無理だよね」

$$dp[q][i] = \min_j\left(dp[q-1][j] + \bigl|j – x[q]\bigr|\right)\tag{2}$$

「それが、できるんですよ」

「えー、セグメント木で可能なのかぁ。どうすればいいんだろう」

「式(2)を詳しく見てみます。まず、数列 dp[q-1][j] が存在します」

「{dp[q-1][0], dp[q-1][1], …, dp[q-1][N-1]} という数列だね」

「これに、関数 |j – x[q]| を足します。この関数の形は分かりますか?」

「x[q] が定数だから、j を変数とする関数 |j – x[q]| の形は、こんな感じだよね」

「数列にこんな {…, 3, 2, 1, 0, 1, 2, 3, …} みたいな数列を足して最小値を取るのは面倒ですよね」

「うん」

「x[q] の左側と右側で分けて考えたら、ちょっと簡単になりそうじゃないですか?」

「なるほど、たしかにそうだね。x[q] より左側では、元の数列に {…, 3, 2, 1, 0} を足したものの最小値を計算して、右側では元の数列に {0, 1, 2, 3, …} を足したものの最小値を計算したら良いんだね。そして、その2つの最小値の小さい方が欲しい値か」

「たとえば、x[q] が 3 (0-indexed) で、元の dp[q][j] が {5, 3, 4, 2, 6, 7, 1} の場合、こんな感じですね」

「カッコ書きの部分はいるの?」

「結局使わないですけど、まとめて計算しちゃうことになります。x[q] の値によってどこまでが必要かが変わるので」

「ふーん。それで、これをどうやって計算するの? 結局、“元の数列 dp[q][j] に一次関数を足した数列” を得る必要があるわけだけど」

「これは、最初からずっと用意しておきます」

「どういうこと?」

「”元の数列に {0, -1, -2, -3, …} を足した列” と “元の数列に {3, 2, 1, 0, -1, …} を足した列” で、最小値の位置は変わらないですよね?」

「後者は、前者の列のすべてに 3 を足したものだから、最小値の位置は変わらず、その値は前者の最小値に 3 を足した値だね」

「その 3 という数はどこから来ましたか?」

「後者の足す列の最初の値が 3 だから、あるいは、後者の足す列の第 3 要素が 0 だから、ということは、さっきの例で言うと x[q] の値が 3 だから、になるのか」

「良いですね」

「なるほど、だからこの値をセグ木で持って…… うん、ここからは僕だけでも解けそうだよ。ありがとう」

「頑張ってください! 私は見てるんで」

「え、なんで見るの」

「他の人が考察する様子ってあんまり見られないじゃないですか」

「気持ちは分かるけど」

「じゃあ、お願いします!」

「えーっと、” dp[q][j] に {0, -1, -2, -3, …} を足した数列” を持つようにすれば、さっきの例の左側の最小値の計算ができるんだな。数列に {3, 2, 1, 0} を足した値の最小値は、数列に {0, -1, -2, -3} を足した値の最小値に 3 を足したものだ」

「ふんふん」

「それと、右側用に、{0, 1, 2, 3, …} を足した数列も必要か。数列に {-3, -2, -1, 0, 1, 2, 3} を足した値の最小値は、数列に {0, 1, 2, 3, 4, 5, 6, 7} を足した値の最小値に、-3 を足したものだ。」

「なるほど」

「この -3 の値は、-x[q] だな。{-3, -2, -1, 0, …} の第 3 要素が 0 だから、第 0 要素は -3 になるんだ」

「ほー」

「やりづらいなぁ……」

「気にしないでください!」

「ください! って言われてもね…… それで、dp[q][x[q-1]] の計算をするときは、x[q] の左側と右側で最小値をセグ木から計算して、それぞれ必要な補正(左側はx[q]を足す、右側はx[q]を引く)をして、その小さい方を dp[q][x[q-1]] とすればいいんだね」

「いいですね」

「式(1)の関係で、全体に |x[q-1] – x[q]| を足すことになってるから、真の dp[q][x[q-1]] から |x[q-1] – x[q]| を引いた値を、dp[q][x[q-1]] としないといけないんだね」

「ふむふむ」

「そして、2本のセグ木には、左側担当には dp[q][j] – j を、右側担当には dp[q][j] + j を持たせてるから、この -j と +j を考慮して、セグ木の値を更新してあげればいいんだね」

「おおー」

「合ってるかわからないけど、とりあえず書いてみるか」

「こんな感じでどうかな」

「あれ、先輩、セグ木のインデックスは 1-indexed じゃなかったんですか?」

「ああ、両方試してみたけど、0-indexed の方が分かりやすい気がしてきて。さて、提出っと…… お、ACだ!」

「おめでとうございます!」

「いやー、難しかったけど勉強になるね。ほぼ全体に定数を足すのはサボれるとか、セグ木に真の値を加工したものを載せるとか、RMQを範囲分割してセグ木を複数持つとか」

「なんか、今回のテクニックをインラインDPって言うらしいですよ。定義はよく知らないんですけど」

「へー、知らないDPテクニックも色々あるんだなあ」

「ところで、妹さんもDPの勉強してるんですよね?」

「うん。この前TDPCの B 問題をやったよ」

「私が妹さんにDP教えてあげてもいいですよ!」

「え、いや、それはいいよ。僕も基本なら教えられるし」

「あれ? 先輩、TDPCはどこまで解いてるんでしたっけ?」

「うっ…… まだ D 問題までしか解いてないけど……」

「あと 2 問しかストック無いじゃないですか! 私ならあと 8 問教えられますよ~」

「いや、僕は後回しになってるだけで、E とか F とかもちゃんと考えれば解けるはず……」

「E って桁DPでしたっけ?」

「ああ、確かそうだったね…… まあ、E 飛ばして F 解くっていうのもアリだし……」

「じゃあ、TDPC の E と F を先輩が自力で解けなかったら、妹さんに DP を教えさせてください!」

「ええ、何の勝負だよ…… っていうか僕にメリット無くない?」

「それはまあ、私の魔の手から妹さんを守れるってことで」

「魔の手って何!? 何するつもりなの!?」

Pocket

スポンサーリンク
レクタングル大
レクタングル大

シェアする

  • このエントリーをはてなブックマークに追加

フォローする