概要

\(N\) 枚の板を \(K\) 色で塗り分ける問題で、隣り合う板が異なる色になるという制約のもとでコスト総和を最小化します。典型的な区間 DP（列 DP）ですが、素朴な遷移では間に合わないため「最小値・2番目の最小値」を使って高速化します。

考察

DP の定義

左から順に決めていくことを考えます。板 \(i\) の色だけが板 \(i+1\) の選択に影響するので、次の DP が自然です。

\[\mathrm{dp}[i][j] = (\text{板 } 1 \sim i \text{ を塗り、板 } i \text{ を色 } j \text{ で塗ったときの最小コスト})\]

初期値は \(\mathrm{dp}[1][j] = C_{1,j}\)、遷移は

\[\mathrm{dp}[i][j] = C_{i,j} + \min_{j' \neq j} \mathrm{dp}[i-1][j']\]

答えは \(\min_j \mathrm{dp}[N][j]\) です。

素朴な実装だと遅い

上の遷移を定義通り実装すると、各 \((i, j)\) に対して \(j' \neq j\) 全体の最小値を取るので \(O(NK^2)\) かかります。\(N \times K \le 10^6\) という制約だけでは \(K\) が \(10^6\) になり得るため（例えば \(N=1, K=10^6\) でも、\(N=1000, K=1000\) なら \(NK^2 = 10^9\)）、これは間に合いません。

高速化の鍵

ここで重要な観察をします。\(\min_{j' \neq j} \mathrm{dp}[i-1][j']\) は、

• \(\mathrm{dp}[i-1]\) の最小値 を与える色を \(j_1\)、その値を \(b_1\)
• \(\mathrm{dp}[i-1]\) の 2 番目に小さい値（同じ値が複数あってもよい、単に「\(j_1\) を除いた最小値」）を \(b_2\)

とすると、

\[\min_{j' \neq j} \mathrm{dp}[i-1][j'] = \begin{cases} b_2 & (j = j_1) \\ b_1 & (j \neq j_1) \end{cases}\]

と書けます。つまり「除外される色が最小値の色と一致するときだけ 2 番目を使う」だけです。

したがって、各行について \(b_1, b_2, j_1\) の 3 つを持っていれば、遷移は各 \(j\) について \(O(1)\) で計算できます。

具体例

\(N=3, K=3\) で

1 5 9
7 2 8
6 4 3

とします。

• \(\mathrm{dp}[1] = (1, 5, 9)\)。\(b_1 = 1\)（\(j_1 = 1\)）、\(b_2 = 5\)。
• \(\mathrm{dp}[2][1] = 5 + 7 = 12\)（色 1 は \(j_1\) なので \(b_2=5\) を使う）、\(\mathrm{dp}[2][2] = 1 + 2 = 3\)、\(\mathrm{dp}[2][3] = 1 + 8 = 9\)。よって \(\mathrm{dp}[2] = (12, 3, 9)\)、\(b_1 = 3\)（\(j_1 = 2\)）、\(b_2 = 9\)。
• \(\mathrm{dp}[3][1] = 3 + 6 = 9\)、\(\mathrm{dp}[3][2] = 9 + 4 = 13\)、\(\mathrm{dop}[3][3] = 3 + 3 = 6\)。最小は \(6\)。

アルゴリズム

1. 1 行目を読みながら \(\mathrm{dp}[j] = C_{1,j}\) を作り、同時に最小値 \(b_1\)・その位置 \(j_1\)・2 番目 \(b_2\) を求める。
2. \(i = 2, \dots, N\) について、\(C_{i,j}\) を読みながら
   • \(\mathrm{ndp}[j] = C_{i,j} + (j = j_1 \text{ なら } b_2 \text{ そうでなければ } b_1)\)
   • 同時に \(\mathrm{ndp}\) の最小値・その位置・2 番目を更新
3. 最後に得られた \(b_1\)（\(= \min_j \mathrm{dp}[N][j]\)）を出力。

最小値と 2 番目の最小値を「1 パスで」求めるには、走査中に

if (v < b1) { b2 = b1; b1 = v; j1 = j; }
else if (v < b2) { b2 = v; }

とすればよいです（この更新順序を間違えないように注意）。

なお、\(N=1\) のときは 1 行目の最小値がそのまま答えになり、上の流れでそのまま処理されます。\(K \ge 2\) が保証されているので必ず解は存在します（\(K=1\) かつ \(N\ge2\) なら不可能ですが、制約で除かれています）。

計算量

• 時間計算量: \(O(NK)\)（入力を読む分と同じオーダー、\(NK \le 10^6\)）
• 空間計算量: \(O(K)\)（DP 配列 2 本のみ。全部の \(C_{i,j}\) を保持する必要はない）

実装のポイント

• 入力を読みながら DP する：\(C\) を \(N \times K\) の 2 次元配列として全部保持しても \(10^6\) 要素なので不可能ではありませんが、行ごとに読み捨てれば \(O(K)\) メモリで済み、キャッシュ効率も良くなります。

• 入出力の高速化：入力は最大 \(10^6\) 個の整数（各最大 10 桁）なので、cin のまま（同期解除なし）だと厳しい場合があります。C++ なら fread による自作高速入力、あるいは ios::sync_with_stdio(false) を推奨します。Python なら sys.stdin.buffer.read() で一括読み込みが必須です。

• オーバーフロー：コストは最大 \(10^9\)、板は最大 \(10^5\) 枚なので総和は最大 \(10^{14}\) 程度。int では溢れるので 64bit 整数（long long）を使います。

• DP 配列のスワップ：swap(dp, ndp)（std::vector の swap はポインタ交換なので \(O(1)\)）でコピーを避けます。実はこの解法では次の行の計算に \(b_1, b_2, j_1\) しか使わないので、dp 配列自体を持たなくても答えは求まります（コード中の dp は実質不要で、値の記録用）。

• 2 番目の最小値の扱い：\(K \ge 2\) なので \(b_2\) は必ず存在します。それでも安全のため初期値を十分大きな値（\(\infty\)）にしておき、\(\infty\) に加算してオーバーフローしないようガードしておくと安心です。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

static char buf[1 << 25];
int bufLen = 0, bufPos = 0;

static inline int gc() {
    if (bufPos == bufLen) {
        bufLen = (int)fread(buf, 1, sizeof(buf), stdin);
        bufPos = 0;
        if (bufLen <= 0) return -1;
    }
    return buf[bufPos++];
}

static inline long long readInt() {
    int c = gc();
    while (c != -1 && (c < '0' || c > '9') && c != '-') c = gc();
    bool neg = false;
    if (c == '-') { neg = true; c = gc(); }
    long long x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = gc();
    }
    return neg ? -x : x;
}

int main() {
    int N = (int)readInt();
    int K = (int)readInt();

    const long long INF = (long long)4e18;

    vector<long long> dp(K), ndp(K);

    // first row
    long long best1 = INF, best2 = INF;
    int idx1 = -1;
    for (int j = 0; j < K; j++) {
        long long c = readInt();
        dp[j] = c;
        if (c < best1) { best2 = best1; best1 = c; idx1 = j; }
        else if (c < best2) { best2 = c; }
    }

    for (int i = 1; i < N; i++) {
        long long nb1 = INF, nb2 = INF;
        int nidx1 = -1;
        for (int j = 0; j < K; j++) {
            long long c = readInt();
            long long prev = (j == idx1) ? best2 : best1;
            long long v = (prev >= INF) ? INF : prev + c;
            ndp[j] = v;
            if (v < nb1) { nb2 = nb1; nb1 = v; nidx1 = j; }
            else if (v < nb2) { nb2 = v; }
        }
        swap(dp, ndp);
        best1 = nb1; best2 = nb2; idx1 = nidx1;
    }

    printf("%lld\n", best1);
    return 0;
}

---

この解説は claude5opus-high によって生成されました。