概要

チェックポイントをいくつか選んで番号の昇順に訪れるとき、訪問数が \(K\) 個以上かつ各地形タイプの訪問回数が偶数になるようにして、移動コストの合計を最小化する問題です。

地形タイプごとの偶奇をビットマスクで管理し、「最後に訪れた地点」「訪問数」「偶奇状態」を持つ動的計画法で解きます。

考察

訪れるチェックポイントの集合を決めると、移動順は番号の昇順に一意に決まります。

例えば訪れるチェックポイントが \(p_1 < p_2 < \cdots < p_s\) なら、経路は必ず

\[ 0 \to p_1 \to p_2 \to \cdots \to p_s \to N+1 \]

です。

したがって、問題は「どのチェックポイントを選ぶか」を決める問題だと考えられます。

しかし、チェックポイントごとに「訪れる / 訪れない」を全探索すると \(2^N\) 通りあり、\(N \leq 150\) なので不可能です。

そこで、以下の性質を利用します。

地形タイプの条件は偶奇だけ見ればよい

各タイプについて、訪問回数が偶数か奇数かだけが重要です。

地形タイプは \(M \leq 8\) 種類なので、偶奇状態を \(M\) bit のビットマスクで表せます。

例えば \(M=3\) のとき、mask の各 bit を次のように対応させます。

• bit \(0\): タイプ \(1\) の訪問回数が奇数か
• bit \(1\): タイプ \(2\) の訪問回数が奇数か
• bit \(2\): タイプ \(3\) の訪問回数が奇数か

あるチェックポイントのタイプが \(t\) なら、そのチェックポイントを訪れることで bit \(t-1\) が反転します。

最終的にすべてのタイプの訪問回数が偶数であるためには、mask が \(0\) になっていればよいです。

訪問数は \(K\) 以上かどうかだけ重要

訪問数については、\(K\) 個未満の間は正確な個数を管理する必要があります。

一方で、すでに \(K\) 個以上訪れている場合は、それ以上の正確な個数は不要です。

そこで、訪問数を

\[ \min(\text{実際の訪問数}, K) \]

として管理します。

つまり、DP 上では訪問数 \(K\) は「\(K\) 個以上訪問済み」を表します。

アルゴリズム

DP を次のように定義します。

\[ dp[c][i][mask] \]

を、

• 最後にいる地点が \(i\)
• 訪問済みチェックポイント数が \(c\)
  • ただし \(c=K\) は「\(K\) 個以上訪問済み」を表す
• 地形タイプの偶奇状態が \(mask\)

であるときの、地点 \(0\) から地点 \(i\) までの最小コストとします。

ここで、\(i\) は \(0\) から \(N\) までです。地点 \(0\) はスタート地点を表します。

初期状態は、

\[ dp[0][0][0] = 0 \]

です。

まだどのチェックポイントにも立ち寄っておらず、偶奇状態もすべて偶数なので mask は \(0\) です。

遷移

状態 \(dp[c][i][mask]\) から、次に訪れるチェックポイントを \(j\) とします。

番号は増加する方向にしか移動できないので、

\[ i < j \leq N \]

です。

チェックポイント \(j\) の地形タイプに対応する bit を type_bit[j] とすると、次の状態は

\[ nc = \min(K, c+1) \]

\[ nmask = mask \oplus type\_bit[j] \]

です。

よって遷移は、

\[ dp[nc][j][nmask] = \min( dp[nc][j][nmask], dp[c][i][mask] + C_{i,j} ) \]

となります。

ここで \(\oplus\) は XOR です。

答え

最後に、どこかのチェックポイント \(i\) から展望台 \(N+1\) に直接移動します。

条件を満たすには、

• 訪問数が \(K\) 個以上
• 偶奇状態が \(0\)

である必要があります。

したがって答えは、

\[ \min_{0 \leq i \leq N} \left( dp[K][i][0] + C_{i,N+1} \right) \]

です。

この値が更新されなければ、条件を満たす経路は存在しないので \(-1\) を出力します。

計算量

\(S = 2^M\) とします。

• 時間計算量: \(O(KN^2 2^M)\)
  • \(K \leq N\) なので、最悪で \(O(N^3 2^M)\)
• 空間計算量: \(O(KN2^M + N^2)\)
  • DP 配列が \(O(KN2^M)\)
  • コスト表が \(O(N^2)\)

実装のポイント

• コストは最大で \(10^9\)、経路長も最大で \(N+1\) 程度あるため、答えは 32 bit 整数に収まりません。long long を使います。

• INF は十分大きい値、例えば 1LL << 62 などにします。

• 地形タイプ \(t_i\) は \(1\) 始まりなので、対応する bit は 1 << (t_i - 1) です。

• 訪問数 \(c=K\) の層では、さらにチェックポイントを訪れても同じ層に遷移します。このときも地点番号は増加するため、\(i\) を小さい順に処理すれば正しく DP が更新されます。

• 実装では、まだ \(K\) 個に到達していない状態について「残りのチェックポイント数が足りない」ような遷移を省くことで高速化しています。これは答えには影響しません。

  ソースコード

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

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

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

    vector<int> type_bit(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        int t;
        cin >> t;
        type_bit[i] = 1 << (t - 1);
    }

    int Q = N + 2;
    vector<long long> C(1LL * Q * Q, 0);
    for (int a = 0; a <= N; a++) {
        for (int b = a + 1; b <= N + 1; b++) {
            cin >> C[1LL * a * Q + b];
        }
    }

    const long long INF = (1LL << 62);
    int S = 1 << M;
    int P = N + 1;

    vector<long long> dp(1LL * (K + 1) * P * S, INF);
    vector<long long> layer_off(K + 1), node_off(P);

    for (int c = 0; c <= K; c++) layer_off[c] = 1LL * c * P * S;
    for (int i = 0; i <= N; i++) node_off[i] = 1LL * i * S;

    dp[layer_off[0] + node_off[0]] = 0;

    for (int c = 0; c <= K; c++) {
        bool capped = (c == K);
        int nc = capped ? K : c + 1;

        int i_start, i_end, max_j;

        if (capped) {
            i_start = (K == 0 ? 0 : K);
            i_end = N - 1;
            max_j = N;
        } else {
            if (c == 0) {
                i_start = i_end = 0;
            } else {
                i_start = c;
                i_end = N - (K - c);
            }
            max_j = N - (K - (c + 1));
        }

        if (i_end < i_start) continue;

        long long dst_layer = layer_off[nc];

        for (int i = i_start; i <= i_end; i++) {
            long long* src = dp.data() + layer_off[c] + node_off[i];
            const long long* crow = C.data() + 1LL * i * Q;

            for (int mask = 0; mask < S; mask++) {
                long long val = src[mask];
                if (val == INF) continue;

                for (int j = i + 1; j <= max_j; j++) {
                    int nmask = mask ^ type_bit[j];
                    long long nv = val + crow[j];
                    long long &ref = dp[dst_layer + node_off[j] + nmask];
                    if (nv < ref) ref = nv;
                }
            }
        }
    }

    long long ans = INF;
    long long final_layer = layer_off[K];

    for (int i = 0; i <= N; i++) {
        long long val = dp[final_layer + node_off[i]];
        if (val == INF) continue;

        long long nv = val + C[1LL * i * Q + (N + 1)];
        if (nv < ans) ans = nv;
    }

    if (ans == INF) cout << -1 << '\n';
    else cout << ans << '\n';

    return 0;
}

---

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