概要

隣り合う板の色が異なるように塗るときの、合計コストの最小値を求めます。動的計画法の遷移を「最小値と、別の色に対応する第2最小値」で高速化すると、\(O(NK)\) 時間で解けます。

考察

最後に使った色を状態にする

板を左から順に塗ることを考えます。次の板に使える色は、直前の板の色によって決まるため、次の状態を定義します。

\(dp[i][j]\)：板 \(1\) から板 \(i\) までを条件を満たすように塗り、板 \(i\) を色 \(j\) にしたときの最小コスト

最初の板には隣接条件がないので、

\(dp[1][j] = C_{1,j}\)

です。板 \(i\) を色 \(j\) にする場合、板 \(i-1\) の色は \(j\) 以外でなければならないため、

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

となります。

答えは、最後の板の色を自由に選んだ

\(\min_{1 \le j \le K} dp[N][j]\)

です。

ただし、各状態で \(j\) 以外の色をすべて調べると、時間計算量は \(O(NK^2)\) となります。\(NK \le 10^6\) でも \(K\) が大きい場合には間に合いません。

最小値と第2最小値で高速化する

必要なのは「特定の色を除いた最小値」です。そこで、前の板について次の3つを保持します。

• minimum：全色の中での最小コスト
• minimumColor：その最小コストを達成する色の1つ
• secondMinimum：minimumColor 以外の色の中での最小コスト

板 \(i\) を色 \(j\) にするとき、前の板までの最小コストは次のように選べます。

• \(j \ne \text{minimumColor}\) なら、minimum を使う。
• \(j = \text{minimumColor}\) なら、同じ色を使えないので secondMinimum を使う。

これにより、各状態を \(O(1)\) 時間で計算できます。

例えば、前の板までのコストが色ごとに \([4,4,9]\) なら、最小値を達成する色として色 \(1\) を選んだ場合、第2最小値は色 \(2\) の \(4\) です。

ここでの第2最小値は「最小値より大きい値」ではありません。別の色に対応する値なら、最小値と同じでもよいことが重要です。

アルゴリズム

各板について、前の板の3つの情報から、現在の板の3つの情報を求めます。

1. 初期値を次のように設定します。
   • minimum = 0
   • secondMinimum = 0
   • minimumColor = -1

コードでは色を \(0\) から \(K-1\) で扱うため、最初の板ではどの色も minimumColor と一致しません。その結果、すべての色について塗装コストだけが計算されます。

1. 現在の板の情報を初期化します。

   • nextMinimum = INF
   • nextSecondMinimum = INF
   • nextMinimumColor = -1

2. 各色 \(j\) のコストを読み込み、現在の板をその色で塗る最小コスト value を求めます。

   • \(j = \text{minimumColor}\) なら、value = cost + secondMinimum
   • それ以外なら、value = cost + minimum

3. value を使って、現在の板の最小値と第2最小値を更新します。

   • value < nextMinimum の場合：
     • これまでの最小値を第2最小値に移す。
     • 最小値を value に更新し、その色を記録する。
   • それ以外で value < nextSecondMinimum の場合：
     • 第2最小値を value に更新する。

4. 全色を処理したら、現在の板の情報を次の板の計算用に引き継ぎます。

すべての板を処理した後、minimum を出力します。

各色の value は動的計画法の遷移式そのものであり、更新によって次の板に必要な最小値・第2最小値が正しく保持されるため、最終的に最小コストが得られます。

計算量

• 時間計算量: \(O(NK)\)
• 空間計算量: \(O(1)\)

各板の各色を1回ずつ処理します。入力されたコストはその場で計算に使うため、コスト表や DP 配列を保存する必要はありません。

実装のポイント

• 合計コストには64ビット整数を使います。
  合計は最大で \(N \times 10^9 \le 10^{14}\) となるため、C++ では long long が必要です。コードの INF = (1LL << 62) は、これより十分大きい値です。

• 最小値と同じ値も第2最小値の候補にします。
  value == nextMinimum の場合も、別の色として第2最小値を更新できる必要があります。コードでは最初の if に入らず、続く else if で処理されます。

• 前の板の情報を途中で上書きしないようにします。
  現在の板の全色を計算する間は、前の板の情報を固定して使います。そのため、更新用に nextMinimum などの変数を用意しています。

• \(N=1\) も同じ処理で扱えます。
  初期化によって最初の板の value は入力コストそのものになり、その最小値が答えになります。

  ソースコード

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

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

    int N, K;
    cin >> N >> K;

    constexpr long long INF = (1LL << 62);
    long long minimum = 0, secondMinimum = 0;
    int minimumColor = -1;

    for (int i = 0; i < N; ++i) {
        long long nextMinimum = INF, nextSecondMinimum = INF;
        int nextMinimumColor = -1;

        for (int j = 0; j < K; ++j) {
            long long cost;
            cin >> cost;

            long long value = cost +
                (j == minimumColor ? secondMinimum : minimum);

            if (value < nextMinimum) {
                nextSecondMinimum = nextMinimum;
                nextMinimum = value;
                nextMinimumColor = j;
            } else if (value < nextSecondMinimum) {
                nextSecondMinimum = value;
            }
        }

        minimum = nextMinimum;
        secondMinimum = nextSecondMinimum;
        minimumColor = nextMinimumColor;
    }

    cout << minimum << '\n';
    return 0;
}

---

この解説は gpt-6-astra-medium によって生成されました。