この記事は 【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみた の子記事です。お読みになる前に親記事をご確認ください。
区間 DP について以下の記事が参考になると思います。
46. ALDS_10_B – 連鎖行列積
Wikipedia の Matrix chain multiplication の記述と問題文の入力例・出力例から、問題文の「スカラー乗算の回数」を行列の積を計算する際に行う行列の成分と成分の乗算の回数だと考えます。
行列の積の定義を確認します。a 行 b 列の行列 A と b 行 c 列の行列 B の積 AB は a 行 c 列の行列です。AB の第 i 行第 j 列の成分 (AB)_{ij} は (AB)_{ij} \coloneqq \sum_{k=1}^{b} A_{ik} B_{kj} で定義します。
まず、a 行 b 列の行列 A と b 行 c 列の行列 B の積 AB を計算する際に行う成分と成分の乗算の回数を考えます。第 i 行第 j 列の成分 (AB)_{ij} を計算するために A_{ik} と B_{kj} の乗算を k = 1, 2, \dots, b の b 回行います。積 AB の成分は ac 個あるため、成分と成分の乗算の回数は b \times ac = abc です。行列の個数 n が 2 のときはこの式を使えば解答できそうです。
次に n > 2 の場合に行列の乗算の順番を全探索するときの計算量を考えます。
積 M_{1} M_{2} M_{3} \dots M_{n} を計算するための行列の乗算の順番は (n – 1)! 通りあります。
計算方法は次の通りです。各 M_{i} M_{i + 1} の間に 1 から n – 1 までの番号を重複なく付けて、その番号の順番で乗算を行うと考えます。1 から n – 1 までの数の順列が乗算の順番と一対一に対応しているため、1 から n – 1 までの数の順列の総数 (n – 1)! が乗算の順番の場合の数になります。
行列の乗算の順番が決まっている場合に M_{1} M_{2} M_{3} \dots M_{n} を計算するための成分と成分の乗算の回数は前述の 2 つの行列の乗算の場合の式 abc を n – 1 回使って求められます。計算量は \Omega(n) です。
以上から、行列の乗算の順番を列挙してから成分と成分の乗算の回数を計算する全探索の計算量は \Omega(n!) となり、時間制限に違反しそうです。
行列 M_{i} の行数を r_i, 列数を c_i とおきます。問題文に明記されていませんが、行列の乗算ができるように c_i = r_{i+1} を仮定します。
行列の積 M_{i} M_{i + 1} \dots M_{j} は i \leq k \leq j – 1 を満たす k について r_i 行 c_k 列の行列 M_i M_{i+1} \dots M_{k} と r_{k+1} (= c_k) 行 c_j 列の行列 M_{k + 1} M_{k + 2} \dots M_j の 2 つの行列の積として表せます。
M_{i} M_{i + 1} \dots M_{j} = \left( M_i M_{i+1} \dots M_{k}\right) \left( M_{k + 1} M_{k + 2} \dots M_j \right)
そのため、最後に M_i M_{i+1} \dots M_{k} と M_{k + 1} M_{k + 2} \dots M_j の乗算を行う場合の成分と成分の乗算の回数は以下の合計です。
- 積 M_i M_{i+1} \dots M_{k} を計算した際に行った成分と成分の乗算の回数
- 積 M_{k + 1} M_{k + 2} \dots M_j を計算した際に行った成分と成分の乗算の回数
- 行列 M_i M_{i+1} \dots M_{k} と行列 M_{k + 1} M_{k + 2} \dots M_j の積を計算する際に行う成分と成分の乗算の回数 r_i c_k c_j
これをもとに区間 DP での解法を検討します。
\mathrm{dp}[i][j] を積 M_i M_{i+1} \dots M_{i + j} を計算する際に行う行列の成分と成分の乗算の回数の最小値とします。以下の更新式を立式できます。
\mathrm{dp}[i][j] = \min_{1 \leq k \leq j} (\mathrm{dp}[i][k-1] + \mathrm{dp}[i+k][j-k] + r_i r_{i+k} c_{i+j})
初期化についてですが、j = 0 のときの積は M_i を表すため、\mathrm{dp}[i][0] は 0 で初期化します。それ以外の \mathrm{dp}[i][j] は成分と成分の乗算の回数の最大値より大きな値にします。r_{i}, c_{i} \leq 100 であるため、2 つの行列の乗算を行う際の成分と成分の乗算の回数は 100^3 以下です。n 個の行列の乗算で行う成分と成分の乗算の回数の最大値は 100^3 * (n – 1) 以下と見積もることができます。n \leq 100 であるため、例えば 100^4 で \mathrm{dp}[i][j] を初期化します。
\mathrm{dp}[i][j] は \mathrm{dp}[i_0][j_0] (i \leq i_0 \leq j, 0 \leq j_0 \leq j – 1) に依存します。そのため、\mathrm{dp}[i][j] の更新は行列の積を計算する際に使用する行列の個数が小さい方 (j が小さい方) から行います。j の for ループが一番外側にあり、i, k のループが続きます。
\mathrm{dp}[1][n – 1] が答えになります。
計算量は j, i, k の三重ループがあるため、O(n^3) = 10^6 程度です。時間制限を満たします。
47. JOI 2015 本選 2 – ケーキの切り分け 2
JOI くんは初めに N 個のピースから好きなピースを 1 つ選び、以降は両端の 2 つのピースから好きな方を選びます。JOI くんの選び方を全列挙すると計算量が \Omega(N 2^{N/2}) になるため、全探索では実行時間制限に違反しそうです。
i 番目から j 番目までのピースがすべて取られている状態は以下の場合でしか成立しません。
- 第 i + 1 番目から第 j 番目までのピースが取られている状態から第 i 番目のピースをとる場合
- 第 i 番目から第 j – 1 番目までのピースが取られている状態から第 j 番目のピースをとる場合
これをもとに区間 DP を用いた解法を検討します。
\mathrm{dp}[i][j] を 2 i 個のピースが j 番目から反時計回りに取られている状態での JOI くんのピースの大きさの合計の最大値とします。場合を分けて \mathrm{dp}[i][j] の更新式が立式できます。
場合 1 A_{j-1}<A_{j + 2i + 1} のとき
2 i + 1 個のピースが j 番目から反時計回りに取られている状態では IOI ちゃんは j + 2i + 1 番目のピースを取るため、2 i + 2 個のピースが j 番目から反時計回りに取られている状態に遷移します。更新式は以下のようになります。
\mathrm{dp}[i + 1][j] = \max(\mathrm{dp}[i + 1][j], \mathrm{dp}[i][j] + A_{j + 2i}, \mathrm{dp}[i][j + 1] + A_{j})
場合 2 A_{j-1}>A_{j + 2i + 1} のとき
2 i + 1 個のピースが j 番目から反時計回りに取られている状態では IOI ちゃんは j-1 番目のピースを取るため、2 i + 2 個のピースが j-1 番目から反時計回りに取られている状態に遷移します。更新式は以下のようになります。
\mathrm{dp}[i + 1][j – 1] = \max(\mathrm{dp}[i + 1][j – 1], \mathrm{dp}[i][j] + A_{j + 2i}, \mathrm{dp}[i][j + 1] + A_{j})
i = 0 はピースを 1 個も取っていない状態であるため、\mathrm{dp}[0][j] は 0 で初期化します。それ以外の \mathrm{dp}[i][j] はすべての A_j を足しても解の候補にならない (例えば負の値になる) ほど小さい値で初期化します。A_j \leq 10^9, N \leq 2000 であるため、例えば -10^{13} で初期化します。
N が偶数のときは \max_{j} \mathrm{dp}[N/2][j] が答えになります。
N が奇数のときは \max_{j} (\mathrm{dp}[(N – 1) / 2][j] + A_{j – 1}) が答えになります。
実装上の小技ですが、j + 2 i などを計算する際に (j + 2 * i) % N と剰余を求めておくと j + 2i > N の場合を分けずに A_{j + 2i} にアクセスできます。
計算量は i, j のループがあるため、O(N^2) = 10^7 程度です。実行時間制限に違反せず求解できます。
\mathrm{dp}[i][j] を i 個のピースが j 番目から反時計回りに取られている状態での JOI くんのピースの大きさの合計の最大値としても求解できます。更新式は i の偶奇で場合分けして立てます。
場合 1 i が偶数のとき
i が偶数のとき、IOI ちゃんの番が終了しているため、JOI くんがケーキを選びます。JOI くんは合計を最大化するため、更新式は以下のようになります。
\mathrm{dp}[i + 1][j] = \max(\mathrm{dp}[i][j] + A_{j + i}, \mathrm{dp}[i][j + 1] + A_j)
場合 2 i が奇数のとき
i が奇数のとき、JOI くんの番が終了しているため、IOI ちゃんがケーキを選びます。IOI ちゃんは両端のうち、大きい方のピースを選ぶため、更新式は以下のようになります。
\begin{aligned}
&\mathrm{dp}[i + 1][j] = \max(\mathrm{dp}[i + 1][j], \mathrm{dp}[i][j]) \quad&\quad (A_{j-1}<A_{j + i}) \\
&\mathrm{dp}[i + 1][j – 1] = \max(\mathrm{dp}[i + 1][j – 1], \mathrm{dp}[i][j]) \quad&\quad (A_{j-1}>A_{j + i})
\end{aligned}
48. AOJ 1611 ダルマ落とし
プロックの対の取り除き方を全探索する場合 \Omega(n!!) の計算量になります。n \leq 300 であるため、時間制限に違反しそうです。
ブロックの対が抜けるかどうかはブロックの塔の現在の状態にのみ依存することに着目して動的計画法で解くことを検討します。
\mathrm{dp}[i][j] を下から j 番目から j + i – 1 番目までのブロックのうち、抜けるブロックの個数の最大値とおきます。以下の場合に分けて更新式を立式できます。
場合 1 最後に両端の j 番目と i + j 番目のブロックの対を抜く場合
以下が成立するとき、最後に両端のブロックの対を抜くことで j 番目から j + i 番目までのブロックをすべて抜けます。
- 第 j + 1 番目から第 j + i – 1 番目までのブロックがすべて抜ける。
- 第 j 番目と第 i + j 番目のブロックの重さの差が 1 以下。
条件を式で表現します。
\mathrm{dp}[i – 1][j + 1] = i – 1, \quad |w_j – w_{i + j}| \leq 1
更新式は \mathrm{dp}[i + 1][j] = i + 1 となります。
場合 2 場合 1 以外の場合
1 \leq k \leq i として \mathrm{dp}[k][j] + \mathrm{dp}[i + 1 – k][j + k] の最大値が \mathrm{dp}[i + 1][j] になります。
\mathrm{dp}[k][j] + \mathrm{dp}[i + 1 – k][j + k] \leq \mathrm{dp}[i + 1][j] については以下の 2 つの方法を組み合わせて \mathrm{dp}[k][j] + \mathrm{dp}[i + 1 – k][j + k] 個のブロックを抜ける j 番目から j + i 番目までの範囲でブロックを抜く方法を作成できることからわかります。
- 第 j 番目から第 j + k – 1 番目までの範囲で \mathrm{dp}[k][j] 個のブロックを抜く方法
- 第 j + k 番目から第 j + i 番目までの範囲で \mathrm{dp}[i + 1 – k][j + k] 個のブロックを抜く方法
ある k で \mathrm{dp}[k][j] + \mathrm{dp}[i + 1 – k][j + k] \geq \mathrm{dp}[i + 1][j] が成立することを示します。
\mathrm{dp}[i + 1][j] を達成する抜き方で抜ける最も下側にあるブロックの番号を l, 最も上側にあるブロックの番号を h とします。また、それぞれのブロックを抜く際に対となるブロックの番号を j_l, j_h とします。
場合2-1 l = j_h = j かつ h = j_l = j + i のとき
場合 1 に一致するため、考慮しません。
場合2-2 l = j_h>j のとき
l の最小性から \mathrm{dp}[i + 1][j] を達成する抜き方では l 番目から j + i 番目のブロックまでの範囲でしかブロックを抜きません。そのため、\mathrm{dp}[i + 1][j] \leq \mathrm{dp}[i + 1 – (l – j)][l] が成り立ちます。
場合2-3 h = j_l<j + i のとき
場合 2-2 と同様に考えて \mathrm{dp}[i + 1][j] \leq \mathrm{dp}[h – j + 1][j] が成立します。
場合2-4 l<j_h または j_l<h のとき
対 (l, j_l), (j_h, h) を抜くためには、それぞれの対の間にあるブロックがすべて抜けている必要があります。そのため、l<j_l<j_h<h が成立します。対 (j_h, h) が抜けることと h の最大性から j \geq j_h を満たす j 番目のブロックは \mathrm{dp}[i + 1][j] を達成する抜き方により以下のいずれかの処理をされます。
- もし j \leq h ならば、j_h 番目以降のブロックと対を成して抜かれる。
- もし j > h ならば、何もされない。
よって \mathrm{dp}[i + 1][j] を達成する抜き方は j 番目から j_h – 1 番目までの範囲でブロックを抜く方法と j_h 番目から j + i 番目までの範囲でブロックを抜く方法に分解できます。以下の不等式が成立します。
\mathrm{dp}[j_h – j][j] + \mathrm{dp}[i + 1 – (j_h – j)][j_h] \geq \mathrm{dp}[i + 1][j]
以上の場合分けから \mathrm{dp}[k][j] + \mathrm{dp}[i + 1 – k][j + k] \geq \mathrm{dp}[i + 1][j] となる k は存在します。ゆえに \mathrm{dp}[k][j] + \mathrm{dp}[i + 1 – k][j + k] の最大値が \mathrm{dp}[i + 1][j] になります。
更新式は以下のようになります。
\mathrm{dp}[i + 1][j] = \max_{1 \leq k \leq i} (\mathrm{dp}[k][j] + \mathrm{dp}[i + 1 – k][j + k])
\mathrm{dp}[i][j] の初期化ですが、更新式に実現不可能な状態遷移が無いため、最小値 0 (一つもブロックを抜かない場合) で初期化して問題ありません。
\mathrm{dp}[n][0] が答えになります。
計算量は \mathrm{dp}[i][j] の一回の更新に O(n) かかるため、1 つのデータセットに対する計算量は O(n^3) = 3 \times 10^7 程度です。データセットが最大 50 あるため、単純にかけると全体で 1.5 \times 10^9 程度になります。添字 j,k の範囲を考えると計算ステップ数は数分の一になると考えられるため、実行時間制限に間に合います。
