■「うーん、オーダーが落ちないなあ……」
●「先輩、競プロですか？」
■「うん。最近、妹に競プロを勧めて、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} の場合、こんな感じですね」
|
1 2 3 4 |
5 3 1 3 6 7 1 +3 2 1 0 1 2 3 -------------- 8 5 2 3 7 9 4 → 最小値は 2 |
↓
|
1 2 3 4 5 6 7 8 9 10 |
5 3 1 3 ( 6 7 1) +3 2 1 0 (-1 -2 -3) ------------------- 8 5 2 3 ( 5 5 -2) → 最小値は 2 と ( 5 3 1) 3 6 7 1 +(-3 -2 -1) 0 1 2 3 ------------------- ( 2 1 0) 3 7 9 3 → 最小値は 3 min(2,3)=2 |
■「カッコ書きの部分はいるの？」
●「結局使わないですけど、まとめて計算しちゃうことになります。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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include <iostream> #include <vector> #include <algorithm> #include <climits> // LLONG_MAX using namespace std; #define repr(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) for(int i=0;i<n;i++) #define reprrev(i,a,b) for(int i=b-1;i>=a;i--) #define reprev(i,n) reprrev(i,0,n) using ll = long long; constexpr long long INFL = LLONG_MAX / 2; class SegTree { public: int n; // 葉の数 vector<ll> dat; // 各ノードの値 ll def = INFL; // デフォルト値（零元） // 区間クエリを決める関数 ll operation(ll a, ll b) { return min(a, b); } // 初期化（n_は必要な要素数） SegTree(int n_) { n = 1; while (n < n_) { n *= 2; } dat = vector<ll>(2 * n - 1, def); } // 場所i(0-indexed)の値をxに更新 void change(int i, ll x) { i += n - 1; dat[i] = x; while (i > 0) { i = (i - 1) / 2; dat[i] = operation(dat[i * 2 + 1], dat[i * 2 + 2]); } } // 場所i(0-indexed)の値を返す ll at(int i) { return dat[i + n - 1]; } // 区間[a,b)の値。ノードk=[l,r)に着目している。 ll _query(int a, int b, int k, int l, int r) { if (b <= a) return def; // 不正な区間の指定 if (r <= a || b <= l)return def; // 交差しない if (a <= l && r <= b)return dat[k]; // a,l,r,bの順で完全に含まれる else { ll c1 = _query(a, b, 2 * k + 1, l, (l + r) / 2); // 左の子 ll c2 = _query(a, b, 2 * k + 2, (l + r) / 2, r); // 右の子 return operation(c1, c2); } } // 内部クエリ_query()を呼び出す ll query(int a, int b) { return _query(a, b, 0, 0, n); } }; int main(void) { int N, Q, A, B; cin >> N >> Q >> A >> B; A--; B--; // 座標を0-indexedに変更する vector<int> x(Q + 1); x[0] = A; // 計算しやすいよう、0番目のクエリの値をAにする rep(i, Q) { cin >> x[i + 1]; x[i + 1]--; // 座標を0-indexedに変更する } // 左側担当と右側担当のセグ木を用意 SegTree dpl(N); // dp[i]-i を格納 SegTree dpr(N); // dp[i]+i を格納 // dp[B] = 0, dp[他] = ∞ dpl.change(B, 0 - B); dpr.change(B, 0 + B); // 全要素に一律に足す値 ll add = 0; repr(q, 1, Q + 1) { // 一律に足す値 int diff = abs(x[q] - x[q - 1]); add += diff; // 更新すべきはdp[x[q-1]]のみ // 新しい値を計算 // dplの区間 [0, x[q]) 、dprの区間 [x[q], N) の最小値をx[q]で補正した値の小さい方） ll newval = min(dpl.query(0, x[q]) + x[q], dpr.query(x[q], N) - x[q]); // diffを足すことを考慮して、[真の値-diff]に更新 dpl.change(x[q - 1], newval - diff - x[q - 1]); dpr.change(x[q - 1], newval - diff + x[q - 1]); } // 最小コストの計算 ll ans = INFL; rep(i, N) { // dp[i]の値は、dpl[i]+i か dpr[i]-i のどちらでも計算できる ans = min(ans, dpl.at(i) + i); } // 全体に足す値を足して答えを出力 cout << ans + add << endl; return 0; } |
●「あれ、先輩、セグ木のインデックスは 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 を教えさせてください！」
■「ええ、何の勝負だよ…… っていうか僕にメリット無くない？」
●「それはまあ、私の魔の手から妹さんを守れるってことで」
■「魔の手って何！？ 何するつもりなの！？」