与えられた n 個の連続ブロックを m グループに分割し、各グループの合計長さの分散を最小化する問題。最終出力は分散値に m² をかけた整数値とする。

分散 v の定義より、各グループ合計を rᵢ、その平均を r̄ とすると：

これを展開・整理すると、目的関数は以下のように変形可能：

ここで、全ブロック長の総和は定数であるため、Σrᵢ² の最小化が本質的な課題となる。

動的計画法による解法

f[i][j] を「先頭 i ブロックを j グループに分割したときの最小二乗和」と定義する。遷移式は以下の通り：

ただし、Sᵢ はブロック長の累積和（S₀ = 0）。

ナイーブ実装では O(n²m) の計算量となり、制約によって部分点止まりとなる。以下は空間を圧縮した2次元DPの例：

// 2層配列による空間最適化
memset(f, 0x3f, sizeof f);
f[0][0] = 0;
for (int grp = 1; grp <= m; ++grp) {
    for (int cur = 1; cur <= n; ++cur) {
        for (int prev = 0; prev < cur; ++prev) {
            ll cost = (prefix[cur] - prefix[prev]);
            f[grp & 1][cur] = min(f[grp & 1][cur],
                f[(grp - 1) & 1][prev] + cost * cost);
        }
    }
}
ll result = m * f[m & 1][n] - prefix[n] * prefix[n];

斜率最適化による高速化

内側ループの min 演算を、直線の傾きと切片の関係として捉えることで、単調キューによる O(n) 遷移が可能になる。

遷移式を再構成：

これは y = ax + b の形式であり、Sₖ を x 座標、f[k][j-1] + Sₖ² を y 座標と見なすと、凸包上の最小切片探索問題に帰着される。

単調キューを用いた最適化コード：

for (int grp = 1; grp <= m; ++grp) {
    int head = 1, tail = 1;
    q[head] = 0;
    for (int i = 1; i <= n; ++i) {
        // 隊列先頭の不要要素を削除
        while (head < tail && 
               slope(grp, q[head+1], q[head]) <= 2LL * prefix[i]) 
            ++head;

        int best = q[head];
        f[grp & 1][i] = f[(grp-1) & 1][best] 
                      + (prefix[i] - prefix[best]) * (prefix[i] - prefix[best]);

        // 隊列末尾の凸性維持
        while (head < tail && 
               cross_check(grp, q[tail], q[tail-1], i)) 
            --tail;

        q[++tail] = i;
    }
}

補助関数の定義例：

inline ll val(int g, int idx) {
    return f[(g-1)&1][idx] + 1LL * prefix[idx] * prefix[idx];
}

inline bool cross_check(int g, int a, int b, int c) {
    return (val(g, a) - val(g, b)) * (prefix[c] - prefix[a])
         >= (val(g, c) - val(g, a)) * (prefix[a] - prefix[b]);
}

実装上の注意点

• すべての数値型は long long で扱う必要がある。
• DP配列は2層ローリングで管理。1次元圧縮は遷移順序の関係で不可。
• 初期状態 f[0][0] = f[1][0] = 0 を忘れずに設定。
• 単調キューには必ず添字0を初期要素として追加。