概要

\(N\) 枚の板を、隣り合う板が同じ色にならないように \(K\) 種類の色で塗るとき、すべての板を塗り分けるための最小コストを求める問題です。動的計画法（DP）を高速化することで、制約内で効率的に解くことができます。

考察

素朴なアプローチ

まず、以下のような動的計画法（DP）の状態を考えます。 - \(dp[i][j] =\) 「板 \(i\) を色 \(j\) で塗ったときの、板 \(1\) から板 \(i\) までの最小総コスト」

板 \(i\) を色 \(j\) で塗るとき、直前の板 \(i - 1\) の色は \(j\) 以外の任意の色 \(k\) (\(k \neq j\)) を選ぶことができます。したがって、遷移式は次のようになります。

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

この遷移を素直に計算しようとすると、以下のようになります。 - 板の枚数: \(N\) - 現在の板の色: \(K\) 通り - 直前の板の色: \(K - 1\) 通りを走査して最小値を探索

この場合、全体の計算量は \(O(N \times K^2)\) となります。 本問題の制約では \(N \times K \leq 10^6\) ですが、\(K\) が最大 \(10^6\) になることがあるため、\(N \times K^2\) は最大で \(10^{12}\) に達し、実行時間制限に間に合わず TLE（実行時間超過）となってしまいます。

高速化のポイント

\(\min_{k \neq j} dp[i - 1][k]\) の部分に着目すると、毎回 \(K\) 個の要素から最小値を探し直していることが無駄であると分かります。

実は、直前の板 \(i - 1\) における DP の値について、「最小値」 と 「2番目に小さい値」 の2つを事前に求めておくだけで、各色 \(j\) に対する遷移を \(O(1)\) で求めることができます。

• 直前の板で最小値をとる色が \(idx_1\) で、その最小値が \(min_1\)
• 直前の板で2番目に小さい値が \(min_2\)

とすると、板 \(i\) を色 \(j\) で塗る場合の最小遷移コストは以下のようになります。 - \(j \neq idx_1\) の場合: 直前で一番コストが小さい色 \(idx_1\) を選べるため、遷移コストは \(min_1\) です。 - \(j = idx_1\) の場合: 同じ色になってしまうため \(idx_1\) は選べません。次にコストが小さい色を選ぶしかないため、遷移コストは \(min_2\) です。

このように「最小値」と「2番目の最小値」を使うことで、各色 \(j\) の更新が \(O(1)\) で行えるようになり、各板に対する計算を \(O(K)\) で処理できます。

アルゴリズム

1. 初期化:
   • \(dp[j] = C_{1, j}\)（板 \(1\) を色 \(j\) で塗るコスト）として配列を初期化します。
2. 板 \(2\) から \(N\) までの更新:
   • 直前の \(dp\) 配列を走査し、以下の値を求めます。
     • 最小値 \(min_1\) とその色のインデックス \(idx_1\)
     • 2番目に小さい値 \(min_2\)
   • 各色 \(j\) (\(0 \leq j < K\)) について、板 \(i\) の新しいコスト \(next\_dp[j]\) を計算します。
     • \(j == idx_1\) ならば \(next\_dp[j] = C_{i, j} + min_2\)
     • \(j \neq idx_1\) ならば \(next\_dp[j] = C_{i, j} + min_1\)
   • \(dp\) 配列を \(next\_dp\) で上書きします。
3. 答えの計算:
   • 板 \(N\) まで塗り終えた後の \(dp\) 配列の最小値が答えとなります。

計算量

• 時間計算量: \(O(N \times K)\)
  • 各板において、最小値と2番目の最小値を求めるのに \(O(K)\)、各色の更新に \(O(K)\) かかります。板は全部で \(N\) 枚あるため、全体の計算量は \(O(N \times K)\) です。
  • 制約より \(N \times K \leq 10^6\) であるため、実行時間制限に十分余裕を持って間に合います。
• 空間計算量: \(O(K)\)
  • 直前の板のDPテーブルのみを保持するため、サイズ \(K\) の配列を2本持つだけで計算できます。\(K \le 10^6\) のためメモリ制限も問題ありません。

実装のポイント

• オーバーフローへの対策:

  • \(C_{i, j} \leq 10^9\) かつ \(N \leq 10^5\) であるため、コストの合計は最大で \(10^{14}\) 程度になります。これは 32bit 符号付き整数の上限（約 \(2 \times 10^9\)）を大きく超えるため、DP テーブルやコストを扱う変数には 64bit 整数型（C++ の long long）を使用します。

• 最小値・2番目の最小値の求め方:

  • ループを1回回す中で、現在の値が \(min_1\) より小さければ \(min_2\) を \(min_1\) で更新してから \(min_1\) を更新し、\(min_1\) 以上だが \(min_2\) より小さければ \(min_2\) のみを更新することで、1回の走査（\(O(K)\)）で2つの値を正しく取得できます。

    ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    if (!(cin >> N >> K)) return 0;

    vector<long long> dp(K);
    for (int j = 0; j < K; ++j) {
        cin >> dp[j];
    }

    for (int i = 1; i < N; ++i) {
        long long min1 = -1, min2 = -1;
        int idx1 = -1;

        for (int j = 0; j < K; ++j) {
            long long val = dp[j];
            if (idx1 == -1 || val < min1) {
                min2 = min1;
                min1 = val;
                idx1 = j;
            } else if (min2 == -1 || val < min2) {
                min2 = val;
            }
        }

        vector<long long> next_dp(K);
        for (int j = 0; j < K; ++j) {
            long long c;
            cin >> c;
            if (j == idx1) {
                next_dp[j] = c + min2;
            } else {
                next_dp[j] = c + min1;
            }
        }
        dp = move(next_dp);
    }

    long long ans = dp[0];
    for (int j = 1; j < K; ++j) {
        ans = min(ans, dp[j]);
    }

    cout << ans << "\n";

    return 0;
}

---

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