概要

円環に並んだ石板を隣同士で順に結合していくときの最小コストを求める問題です。
本質は「区間マージDP（最適二分木型DP）」で、円環は配列を2倍にして「長さ \(N\) の連続区間」を全探索することで処理できます。

考察

まず、直線上の同種問題を考えると、区間 \([l,r]\) を1つにまとめる最小コストは

• 最後にどこで2つの部分区間に分けたか（分割点 \(k\)）
• 左右をまとめるコスト
• 最後に左右を結合するコスト（区間和）

で表せます。
つまり典型的な区間DPです。

なぜ素朴解法がだめか

• 結合順はカタラン数オーダーで爆発し、全探索は不可能です。
• 通常の区間DPでも
  \(dp[l][r] = \min_{l \le k < r}(dp[l][k]+dp[k+1][r]+\text{sum}(l,r))\)
  をそのまま回すと \(O(N^3)\)。
• 本問は円環なので、単純化しても実質 \(N=1000\) では \(O(N^3)\) は重いです。

円環をどう扱うか

円環は開始位置が決まっていないだけなので、配列を2倍にして
\(B = A + A\)
とし、「長さ \(N\) の連続区間」 \([s, s+N-1]\) をすべて候補にします。
各候補区間を直線問題として解き、最小を取れば円環の答えになります。

高速化のポイント

このDPは Knuth最適化 が使える形です。
最適分割点を opt[l][r] とすると、次が成り立つため

\(opt[l][r-1] \le opt[l][r] \le opt[l+1][r]\)

分割点探索範囲を狭められ、全体を \(O(N^2)\) にできます。
提出コードはこの単調性を使って k のループを短くしています。

アルゴリズム

1. 入力配列 A を2倍して B = A + A を作る（長さ 2N）。
2. 累積和 pref を作り、区間和を \(O(1)\) で取得できるようにする。
3. DP定義：
   • dp[l][r]：B[l..r] を1枚にする最小コスト
   • opt[l][r]：そのときの最適分割点
4. 初期値：
   • 長さ1区間はコスト0（既に1枚）
   • opt[i][i] = i
5. 区間長 length = 2..N の順に更新：
   • total = sum(l,r)
   • 探索範囲を
     left = opt[l][r-1], right = opt[l+1][r]
     に制限（必要なら l..r-1 にクリップ）
   • k を left..right で試し
     dp[l][k] + dp[k+1][r] + total
     の最小を採用
6. 最後に、すべての開始位置 s=0..N-1 について
   dp[s][s+N-1] の最小を答えとする。

計算量

• 時間計算量: \(O(N^2)\)（Knuth最適化つき区間DP）
• 空間計算量: \(O(N^2)\)（dp, opt がともに \(2N \times 2N\)）

実装のポイント

• コストは最大で非常に大きくなるので、INF = 10**30 など十分大きい値を使う。

• 区間和は毎回足し直さず、必ず累積和で \(O(1)\) 取得する。

• opt の範囲は理論上単調でも、実装では配列外・不正範囲を防ぐため l と r-1 でクリップしている点が重要です。

  ソースコード

import sys


def main():
    input = sys.stdin.readline
    N = int(input().strip())
    A = list(map(int, input().split()))

    B = A + A
    pref = [0] * (2 * N + 1)
    for i in range(2 * N):
        pref[i + 1] = pref[i] + B[i]

    INF = 10**30
    M = 2 * N

    dp = [[0] * M for _ in range(M)]
    opt = [[0] * M for _ in range(M)]

    for i in range(M):
        opt[i][i] = i

    for length in range(2, N + 1):
        for l in range(0, M - length + 1):
            r = l + length - 1
            total = pref[r + 1] - pref[l]

            left = opt[l][r - 1]
            right = opt[l + 1][r]
            if left < l:
                left = l
            if right > r - 1:
                right = r - 1

            best = INF
            bestk = left
            for k in range(left, right + 1):
                v = dp[l][k] + dp[k + 1][r] + total
                if v < best:
                    best = v
                    bestk = k

            dp[l][r] = best
            opt[l][r] = bestk

    ans = INF
    for s in range(N):
        ans = min(ans, dp[s][s + N - 1])

    print(ans)


if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。