概要

この問題は、地点 \(0\)（麓）から地点 \(N+1\)（山頂）まで移動する際に、いくつかのチェックポイントを経由して移動コストの総和を最小化する問題です。 経由するチェックポイントには、「合計で \(K\) 個以上立ち寄る」、「各地形タイプに立ち寄る回数がすべて偶数回である」という \(2\) つの制約があります。

考察

1. 状態の整理と制約の分解

チェックポイントの経由の仕方を決めるにあたり、以下の情報を管理する必要があります。 1. 現在どのチェックポイントにいるか（次の移動コスト \(C_{i, j}\) を計算するため） 2. これまでに立ち寄ったチェックポイントの総数（\(K\) 個以上という条件を満たすため） 3. 各地形タイプに立ち寄った回数の偶奇（すべて偶数回という条件を満たすため）

ここで、地形タイプの数 \(M\) に注目すると、 \(1 \leq M \leq 8\) と非常に小さいことがわかります。 各地形タイプの訪問回数の「偶奇（奇数なら \(1\)、偶数なら \(0\)）」は、 \(2^M\) 通りのビットマスク（\(0\) から \(2^M-1\) までの整数）としてコンパクトに表現できます。例えば \(M=3\) で、タイプ \(1, 3\) が奇数回、タイプ \(2\) が偶数回なら、ビットは 101（10進数で \(5\)）となります。

2. 動的計画法（DP）の設計

\(N \leq 150\) とこちらも十分に小さいため、上記の情報をすべて状態に持たせた動的計画法（DP）が適用できます。

以下のように DP テーブルを定義します。

dp[i][c][mask] := 最後に立ち寄ったチェックポイントが \(i\) で、これまでに立ち寄った個数が \(c\) 個であり、各地形タイプの訪問回数の偶奇状態が mask であるときの、消費体力の最小値。

3. 状態遷移

地点 \(i\) から次に立ち寄るチェックポイント \(j\) （\(i < j \leq N\)）を全探索します。 チェックポイント \(j\) の地形タイプを \(t_j\)（0-indexed で \(t_j - 1\) 番目のビット）とすると、遷移は以下のようになります。

• 遷移先: dp[j][c + 1][next_mask]
• 遷移式の更新: $\(dp[j][c + 1][next\_mask] = \min(dp[j][c + 1][next\_mask], dp[i][c][mask] + C_{i, j})\)\( ここで、`next_mask` は `mask` の \)t_j - 1$ 番目のビットを反転させたものです（ビット XOR 演算 mask ^ (1 << (t_j - 1)) で計算できます）。

最後に、山頂（地点 \(N+1\)）への移動を考えます。 最後に立ち寄った地点を \(i\)（\(0 \leq i \leq N\)）とすると、立ち寄った個数 \(c\) が \(K\) 以上、かつ偶奇状態が \(0\)（すべて偶数回訪問）である状態から、直接山頂へ移動するコスト \(C_{i, N+1}\) を足したものの最小値が答えになります。

アルゴリズム

1. 初期化:

   • dp テーブルのすべての値を十分大きな値（\(\infty\)）で初期化します。
   • 初期状態として、麓（地点 \(0\)）にいて、立ち寄り回数 \(0\)、マスク \(0\) のコストを \(0\) とします（dp[0][0][0] = 0）。

2. DP の更新:

   • \(i\) を \(0\) から \(N\) まで、 \(c\) を \(0\) から \(i\) まで、 mask を \(0\) から \(2^M-1\) までループさせます。
   • dp[i][c][mask] が \(\infty\) でない場合、次に進む地点 \(j\) （\(i < j \leq N\)）をすべて探索し、DP テーブルを更新します。

3. 答えの集計:

   • 最後に立ち寄った地点 \(i\) （\(0 \leq i \leq N\)）と、立ち寄り回数 \(c\) （\(K \leq c \leq i\)）について、dp[i][c][0] + C[i][N+1] の最小値を求めます。
   • 最小値が \(\infty\) のままであれば、条件を満たす経路が存在しないため -1 を出力し、そうでなければ最小値を出力します。

計算量

• 時間計算量: \(O(N^3 \cdot 2^M)\) DP の状態数が \(O(N^2 \cdot 2^M)\) あり、各状態からの遷移が \(O(N)\) 通り存在するため、全体のループ回数は最大で \(\sum_{i=0}^{N} \sum_{c=0}^{i} 2^M \cdot (N - i) \approx \frac{1}{6} N^3 \cdot 2^M\) となります。 \(N = 150, M = 8\) のとき、最悪でも約 \(1.4 \times 10^8\) 回の単純なループとなり、実行時間制限内に余裕で間に合います。

• 空間計算量: \(O(N^2 \cdot 2^M)\) DP テーブルのサイズは \((N+1) \times (N+1) \times 2^M\) です。 \(155 \times 155 \times 256 \times 8 \text{ bytes} \approx 49 \text{ MB}\) となり、メモリ制限（通常 256MB 〜 1024MB）に十分収まります。

実装のポイント

• ビット演算による高速化: 地形タイプ \(t_i\) は \(1\) から \(M\) までの値をとるため、 \(0\) から \(M-1\) の値に直す（0-indexed にする）ために t[j-1] - 1 を用いてビットシフト 1 << (t[j-1] - 1) を行います。 偶奇の反転は XOR 演算子 ^ を使うことで、高速かつ簡潔に実装できます。

• インデックスの境界: 立ち寄るチェックポイントの最小個数 \(K\) が \(0\) の場合、一度もチェックポイントに立ち寄らずに \(0 \to N+1\) へ直接移動する経路（\(s=0\)）も正しく考慮される必要があります。 本実装では \(i=0, c=0\) の状態から \(C_{0, N+1}\) を足して集計する処理が含まれているため、このケースも正しくカバーされています。

  ソースコード

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

using namespace std;

const long long INF = 1e18;

// dp[i][c][mask]
// i: current checkpoint (0 to N)
// c: number of visited checkpoints (0 to N)
// mask: parity of visits to each terrain type (0 to 2^M - 1)
long long dp[155][155][256];

int main() {
    // Optimize standard I/O operations for performance
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

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

    // C[i][j] stores the cost of direct movement from i to j
    vector<vector<long long>> C(N + 1, vector<long long>(N + 2));
    for (int i = 0; i <= N; ++i) {
        for (int j = i + 1; j <= N + 1; ++j) {
            cin >> C[i][j];
        }
    }

    // Initialize DP table with infinity
    for (int i = 0; i <= N; ++i) {
        for (int c = 0; c <= N; ++c) {
            for (int mask = 0; mask < (1 << M); ++mask) {
                dp[i][c][mask] = INF;
            }
        }
    }

    // Base case: starting at point 0, with 0 checkpoints visited and empty mask
    dp[0][0][0] = 0;

    // DP transitions
    for (int i = 0; i <= N; ++i) {
        for (int c = 0; c <= i; ++c) {
            for (int mask = 0; mask < (1 << M); ++mask) {
                long long val = dp[i][c][mask];
                if (val == INF) continue;

                for (int j = i + 1; j <= N; ++j) {
                    int next_mask = mask ^ (1 << (t[j - 1] - 1));
                    if (dp[j][c + 1][next_mask] > val + C[i][j]) {
                        dp[j][c + 1][next_mask] = val + C[i][j];
                    }
                }
            }
        }
    }

    // Find the minimum cost to reach the observatory (N + 1)
    long long ans = INF;
    for (int i = 0; i <= N; ++i) {
        for (int c = K; c <= i; ++c) {
            if (dp[i][c][0] != INF) {
                ans = min(ans, dp[i][c][0] + C[i][N + 1]);
            }
        }
    }

    if (ans == INF) {
        cout << -1 << "\n";
    } else {
        cout << ans << "\n";
    }

    return 0;
}

---

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