問題
$N$ 個の行列 $M_1, M_2, \ldots, M_N$ が与えられる。$M_i$ は $d_{i-1} \times d_i$ 行列（$d_0, d_1, \ldots, d_N$ が入力）。これらを順番に全て掛け合わせるとき、スカラー乗算の回数を最小化する括弧配置を求め、最小スカラー乗算回数を答えよ。
さらに、「最適配置が複数ある場合の辞書順最小括弧列」も出力せよ。
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $N$ | $1 \le N \le 500$ | 行列数 |
| $d_i$ | $1 \le d_i \le 500$ | 次元 |
| $d_i \times d_k \times d_j$ | 最大 $1.25 \times 10^8$ | 各掛け算コスト |
入出力例
入力例1
4
10 30 5 60 2出力例1
4500
((M1(M2M3))M4)入力例2
3
2 3 4 5出力例2
58
(M1(M2M3))概念図: 区間 DP の遷移
ヒント
ヒント1（方向性）
区間 DP の典型問題。$dp[i][j]$ = $M_i$ から $M_j$ までを掛け合わせるときの最小スカラー乗算回数と定義する。最後にどこで分割するか（$k$）を決めると2つの部分問題に分解できる。
ヒント2（アプローチ）
漸化式: $dp[i][j] = \min_{k=i}^{j-1}(dp[i][k] + dp[k+1][j] + d_{i-1} \cdot d_k \cdot d_j)$
区間長 $\ell = 2, 3, \ldots, N$ の順に計算する。$\text{split}[i][j] = k$ も記録して括弧列復元に使う。
ヒント3（ほぼ答え）
dp = [[float('inf')] * (N + 1) for _ in range(N + 1)]
split = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
dp[i][i] = 0
for length in range(2, N + 1):
for i in range(1, N - length + 2):
j = i + length - 1
for k in range(i, j):
cost = dp[i][k] + dp[k+1][j] + d[i-1] * d[k] * d[j]
if cost < dp[i][j]:
dp[i][j] = cost
split[i][j] = k
def reconstruct(i, j):
if i == j: return f'M{i}'
k = split[i][j]
return f'({reconstruct(i, k)}{reconstruct(k+1, j)})'模範解答
import sys
input = sys.stdin.readline
def solve():
N = int(input())
d = list(map(int, input().split()))
INF = float('inf')
dp = [[INF] * (N + 1) for _ in range(N + 1)]
split = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
dp[i][i] = 0
for length in range(2, N + 1):
for i in range(1, N - length + 2):
j = i + length - 1
for k in range(i, j):
cost = dp[i][k] + dp[k+1][j] + d[i-1] * d[k] * d[j]
if cost < dp[i][j]:
dp[i][j] = cost
split[i][j] = k
print(dp[1][N])
sys.setrecursionlimit(10000)
def reconstruct(i, j):
if i == j:
return f'M{i}'
k = split[i][j]
left = reconstruct(i, k)
right = reconstruct(k + 1, j)
return f'({left}{right})'
print(reconstruct(1, N))
solve()Step-by-Step 解説
Step 1: 問題の定式化
| 括弧配置 | コスト |
|---|---|
| $(M_1 M_2) M_3$ | $d_0 d_1 d_2 + d_0 d_2 d_3$ |
| $M_1 (M_2 M_3)$ | $d_1 d_2 d_3 + d_0 d_1 d_3$ |
Step 2: DP の漸化式
$$dp[i][j] = \min_{k=i}^{j-1} \bigl(dp[i][k] + dp[k+1][j] + d_{i-1} \cdot d_k \cdot d_j\bigr)$$
- $dp[i][k]$: $M_i \cdots M_k$ を1つにまとめるコスト（結果は $d_{i-1} \times d_k$ 行列）
- $dp[k+1][j]$: $M_{k+1} \cdots M_j$ を1つにまとめるコスト（結果は $d_k \times d_j$ 行列）
- $d_{i-1} \cdot d_k \cdot d_j$: 2つをかけ合わせるコスト
Step 3: 計算量
| 操作 | 計算量 |
|---|---|
| DP テーブル計算 | $O(N^3)$ |
| 括弧列復元 | $O(N)$ |
| 空間 | $O(N^2)$ |
四辺形不等式（Knuth 最適化）を適用すると $O(N^2)$ にできるが、$N \le 500$ なので $O(N^3)$ で十分。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 区間長の順序間違い | dp[i][j] 計算時に dp[i][k] が未計算 | 外ループを区間長 $\ell$ にする |
| インデックスのずれ | $d$ の添字と行列番号のずれ | $M_i$ は $d[i-1] \times d[i]$ を明確に |
| コスト計算式の誤り | $d[i-1] \times d[k] \times d[j]$ の位置 | 中間次元は $d_k$（分割点の次元） |
次のステップ
- 発展問題: Optimal Binary Search Tree（最適 BST・Knuth 最適化で $O(N^2)$）
- 発展問題: 石の合体問題（区間 DP + 四辺形不等式）
自己評価
理解度: / /
自分の回答:
気づき・メモ: