Day 158-Q3 | 合体と挿入し直しの過程

問題

一列に並んだ $N$ 個のスライム（石の山）があり、$i$ 番目の大きさは $a_i$ である。隣り合う 2 つを選んで合体させる操作を、全体が 1 つになるまで $N-1$ 回繰り返す。大きさ $x$ と $y$ を合体させると大きさ $x+y$ のスライムになり、コスト $x+y$ がかかる。

コストの総和の最小値を求めよ。

入力形式

N
a_1 a_2 ... a_N

制約

#	条件
1	$1 \le N \le 5000$
2	$1 \le a_i \le 10^6$

入出力例

入力例1

4
4 1 2 3

出力例1

（$1+2=3$ → $[4,3,3]$、$3+3=6$ → $[4,6]$、$4+6=10$。$3+6+10=19$）

参考: EDPC N「Slimes」（https://atcoder.jp/contests/dp/tasks/dp_n 、2026-09-23 参照）は $N \le 400$ で $O(N^3)$ の区間 DP が想定解。POJ 1738「An old Stone Game」は $N \le 50000$ で Garsia–Wachs 法が想定解として知られる。本問は Python で $O(N^2)$ の区間 DP（Knuth 最適化）がぎりぎり苦しく、Garsia–Wachs 法なら余裕がある大きさに設定した。

概念図：合体と挿入し直しの過程

ヒント（クリックで段階的に開示）

ヒント1（方向性）

合体の手順は「葉の並び順を保った二分木」と1対1に対応し、総コスト = $\sum_i a_i \times (\text{葉 } i \text{ の深さ})$。これは 最適アルファベット順二分木（Hu–Tucker 問題）そのもの。ハフマン符号は並び順を無視できるので使えない。

ヒント2（アプローチ）

Garsia–Wachs 法（1977）: 両端に $+\infty$ を置いた列で、

$a_{k-1} \le a_{k+1}$ となる 最小の $k$ を探し、$a_{k-1}$ と $a_k$ を合体させて $t = a_{k-1} + a_k$ とする
2 つを消し、$t$ を「左に向かって最初に現れる $t$ 以上の要素」の すぐ右 に挿入し直す
これを 1 つになるまで繰り返し、足した $t$ の総和が答え

「並び順を崩して挿入し直す」のに答え（コスト）は正しい、というのがこの算法の核心で、証明は Knuth『TAOCP』第3巻 §6.2.2 にある。

ヒント3（誘導）

INF = float("inf")
a = [INF] + a + [INF]
k = 2
while len(a) > 3:
    while a[k-2] > a[k]:   # a[k-2] <= a[k] となる最小の k を探す
        k += 1
    t = a[k-2] + a[k-1]; total += t
    del a[k-2:k]
    j = k - 2
    while a[j-1] < t:      # 左へ、t 以上の要素が見つかるまで
        j -= 1
    a.insert(j, t)
    k = max(2, j - 1)      # 挿入位置より左は条件が変わらないので再走査しない

模範解答 (Python)

模範解答を表示する（まず自力で解いてから）

import sys

INF = float("inf")


def garsia_wachs(weights):
    a = [INF] + list(weights) + [INF]
    total = 0
    k = 2
    while len(a) > 3:
        while a[k - 2] > a[k]:
            k += 1
        t = a[k - 2] + a[k - 1]
        total += t
        del a[k - 2:k]
        j = k - 2
        while a[j - 1] < t:
            j -= 1
        a.insert(j, t)
        k = max(2, j - 1)
    return total


def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    a = [int(x) for x in data[1:1 + n]]
    print(garsia_wachs(a))


main()

計算量: 本実装は最悪 $O(N^2)$（リストの削除・挿入が $O(N)$ の memmove、左方向の探索が $O(N)$）。ただし重い部分は C レベルの memmove で、実測では Knuth 最適化 DP より 40 倍以上速い（検証ログ参照）。平衡二分探索木を使うと $O(N \log N)$ にできる（「迷った他案」参照）。

Step-by-Step 解説

1区間 DP の復習（基準）

$dp[l][r] = \min_{l \le m < r} (dp[l][m] + dp[m+1][r]) + \sum_{i=l}^{r} a_i$ で $O(N^3)$。コスト関数 $w(l,r)=\sum a$ は四角不等式と単調性を満たすので Knuth 最適化（$opt[l][r-1] \le opt[l][r] \le opt[l+1][r]$）で $O(N^2)$ になる（本シリーズ Day020 Q4・Day115 Q4）。

2「局所的に一番軽いペア」から合体してよい

$a_{k-1} \le a_{k+1}$ を満たす最小の $k$ では、それより左の列は $a_0 > a_2 > a_4 \cdots$ 型に「2つおきに狭義減少」している。この位置のペア $(a_{k-1}, a_k)$ は、最適な二分木で 兄弟（同じ親の2つの子） になっているものが必ず存在する——これが Garsia–Wachs（およびその元になった Hu–Tucker）の補題。

3挿入し直しても深さの総和は変わらない

合体した $t$ を「左で最初に $t$ 以上になる要素の右」に移すと、葉の並び順は崩れる。それでも、移動後の列で得られる最適木の 各葉の深さの多重集合 は元の列でも実現できる（深さ列から順序を保った木を再構成できる）。したがってコストの値は正しい。ただし 木の形そのもの を出力したい場合は、最後に「各葉の深さ」を記録して並び順どおりに木を組み立て直す第2段階が必要（本問はコストだけなので不要）。

4入力例1を手で追う

$[\infty, 4, 1, 2, 3, \infty]$

$k=2$: $a_0=\infty > a_2=1$。$k=3$: $a_1=4 > a_3=2$。$k=4$: $a_2=1 \le a_4=3$ → $1+2=3$ を合体（コスト 3）
残り $[\infty,4,3,\infty]$ の $4$ の右（$4 \ge 3$）に挿入 → $[\infty,4,3,3,\infty]$
$k=4$ で $a_2=3 \le a_4=\infty$ → $3+3=6$ を合体（コスト 6）。左へ探すと $4<6$ なので通り過ぎ、$\infty$ の右に挿入 → $[\infty,6,4,\infty]$（並び順が入れ替わる）
最後に $6+4=10$（コスト 10）。合計 $3+6+10=19$

5k = max(2, j-1) の再開位置

挿入位置 $j$ より左の要素は一切動いていないので、そこでは「$a_{i-2} > a_i$」が成り立ったまま。再判定が必要なのは $t$ が関わる $j-1$ 以降だけ。毎回 $k=2$ からやり直すと、$N=20000$ のランダム入力で 3.356 秒 → 再開版 2.266 秒（実測）。

迷った他案と採らなかった理由

案	計算量	採否	理由
区間 DP	$O(N^3)$	比較用のみ	$N=200$ で 0.087 秒、$N=5000$ では $\approx 1.4\times10^5$ 倍（導出）で不可能
Knuth 最適化 DP	$O(N^2)$	比較用のみ	$N=2000$ で 0.896 秒（実測）、$N=5000$ で約 5.6 秒と見積もる（$N^2$ 比 6.25 倍、導出）。$N \le 2000$ なら証明が単純なこちらを選ぶ
ハフマン符号（ヒープで最小 2 つを合体）	$O(N \log N)$	誤り	隣接制約を無視するので下界にしかならない。入力例 $[4,1,2,3]$ では 19 と偶然一致するが、$[1,10,1]$ ではハフマンが $2+12=14$、正解は $11+12=23$ と食い違う
Hu–Tucker 法（1971）	$O(N \log N)$	不採用	Garsia–Wachs と同じ答えを出す先行算法だが、「互換ペア」の管理が複雑で実装量が数倍
Garsia–Wachs ＋平衡木/連結リスト＋ヒープ	$O(N \log N)$	扱わない	POJ 1738（$N \le 50000$）級なら必要。Python で平衡木を書くと定数倍が重く、$N \le 5000$ ではリスト版の方が速いと判断（未計測。$N$ が $10^5$ 級に変わったら実装して比較する。本セッションでリスト版は $N=10^5$ ランダムで 59.3 秒、減少列で 222.7 秒かかった）
Garsia–Wachs リスト版（本解）	最悪 $O(N^2)$	採用	20 行。$N=5000$ の最悪入力（減少列）でも 0.509 秒（実測）

よくあるミス

ミス	原因	正しい書き方
番兵 $+\infty$ を付けない	端で `a[k-2]` や `a[j-1]` が範囲外、または負の添字で末尾を参照（Python では静かに誤答）	両端に `INF` を置く
条件を $a_{k-1} < a_{k+1}$（狭義）にする	等号の扱いの違い	$\le$ で「最小の $k$」。本解ではランダム 2000 件（同値を多く含む）で区間 DP と一致を確認
合体した $t$ を元の位置に戻す	並び順を保たないと不安に感じる	左方向の「$t$ 以上の要素の右」へ移すのが算法の一部。元の位置に置くとただの貪欲法になり誤答
ハフマン符号で解く	隣接制約を見落とす	上の表の反例 $[1,10,1]$
木の形まで出そうとしてそのまま出力	Step 3 の順序の崩れ	深さを記録し、第2段階で並び順どおりに組み直す

次のステップ

発展1: 各葉の深さから並び順を保った二分木を組み立てる第2段階を実装し、最適アルファベット順符号（辞書順を保つ可変長符号）を出力する
発展2: Garsia–Wachs を連結リスト＋ヒープで $O(N \log N)$ にし、$N=10^5$ でリスト版の 59.3 秒と比較する
扱わなかった範囲: 合体コストが和でない一般の区間 DP（四角不等式が成り立たないと Garsia–Wachs も Knuth も使えない）、円環状の並び（EDPC にない変種。直線版を 2 周分並べる区間 DP に帰着するのが定石で、Garsia–Wachs を円環に直接使えるかは本問では扱わない）

検証ログ（本セッションで実行した数値）

入力例1: Garsia–Wachs 19、区間 DP 19。追加例 $[1,2,3,4,5]$ で 33
ランダムテスト: $N \le 12$、値域 $[1,3]$・$[1,20]$・$[1,1000]$ を混ぜた（同値が多いケースを含む）計 3000 件（再開なし版 1000 件＋再開版 2000 件）で $O(N^3)$ 区間 DP と比較 → 不一致 0 件
性能（実測）: $N=200$ で区間 DP 0.087 秒 / Garsia–Wachs 0.0002 秒。$N=2000$ で Knuth DP 0.896 秒 / Garsia–Wachs 0.020 秒（答え一致）
性能（実測、$N=5000$）: ランダム 0.139 秒、減少列 0.509 秒、増加列 0.244 秒、全要素同じ 0.009 秒
上限を超えた参考値（実測）: $N=10^5$ でランダム 59.3 秒、減少列 222.7 秒 → リスト版の $O(N^2)$ が効いてくる境目。制約を $N \le 5000$ にした根拠
ハフマンの反例 $[1,10,1]$: 正解 23（区間 DP で確認）
検証スクリプト: スクラッチパッドの q3.py・q3b.py・q3c.py（上記は実行結果の転記）

自己評価

完全理解おおむね理解要復習

Day 158-Q3 — Garsia–Wachs 法（石の併合を区間DPなしで解く）

問題