概要

チェックポイントの立ち寄り方に「最小個数」と「各地形タイプの訪問回数がすべて偶数」という制約がある中での、スタートからゴールまでの最小コスト経路を求める問題です。 制約の \(M \le 8\) という小ささに着目し、ビットDP（Bit DP）と通常の動的計画法（DP）を組み合わせることで効率的に解くことができます。

考察

1. 状態の表現方法

この問題では、移動の途中で「今どのチェックポイントにいるか」「これまでに何個のチェックポイントに立ち寄ったか」「各地形タイプを何回訪れたか（奇数回か偶数回か）」を管理する必要があります。

• 現在地: 最後に立ち寄ったチェックポイントを \(i\) とします。
• 立ち寄った個数: 個数 \(s\) が \(K\) 以上である必要があります。\(K\) 個以上立ち寄った後は、それ以上個数を正確にカウントする必要はなく「\(K\) 個以上立ち寄った」という状態にまとめられます。したがって、立ち寄り数は \(0\) から \(K\) までの \(K+1\) 通りで管理できます。
• 地形タイプの訪問回数の奇偶: 各地形タイプの訪問回数が偶数である必要があります。\(M \le 8\) と非常に小さいため、各地形タイプの訪問回数の奇偶（奇数 = 1, 偶数 = 0）を \(M\) ビットの整数（マスク）で表現できます。状態数は \(2^M \le 256\) 通りです。

2. ナイーブなアプローチと改善

すべての立ち寄り方の組み合わせを探索すると、チェックポイントの選び方だけで \(2^N\) 通りあり、\(N \le 150\) では到底間に合いません。 しかし、上記の3つの情報（現在地、立ち寄り数、奇偶マスク）を状態とするDPを定義すれば、同じ状態に達する経路のうち「最小コストのもの」だけを保持すればよいため、探索空間を劇的に削減できます。

アルゴリズム

DPテーブルの定義

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

\[dp[i][j][mask] := \text{最後に立ち寄ったチェックポイントが } i \text{ で、立ち寄り数が } j \text{（最大 } K \text{）、訪問奇偶状態が } mask \text{ であるときの最小コスト}\]

• \(0 \le i \le N\)
• \(0 \le j \le K\)
• \(0 \le mask < 2^M\)

初期状態

スタート地点 \(0\)（まだどのチェックポイントにも立ち寄っていない）から始めます。 - \(dp[0][0][0] = 0\) - それ以外のすべての要素は \(\infty\)（未到達）

遷移

現在地 \(i\) から、次に立ち寄るチェックポイント \(next\_i\) （\(i < next\_i \le N\)）を全探索します。

現在の状態が \(dp[i][j][mask]\) のとき、遷移先は次のようになります。 - 次の立ち寄り数: \(next\_j = \min(j + 1, K)\) - 次の奇偶状態: \(next\_mask = mask \oplus (1 \ll t_{next\_i})\) （\(\oplus\) はビットごとの排他的論理和 XOR） - 遷移式: $\(dp[next\_i][next\_j][next\_mask] = \min(dp[next\_i][next\_j][next\_mask], dp[i][j][mask] + C_{i, next\_i})\)$

答えの計算

すべてのDPの遷移が終わった後、ゴール地点 \(N+1\) への移動コストを足して最小値を求めます。 条件を満たす状態は、立ち寄り数が \(K\)（\(K\) 個以上）で、奇偶状態が \(0\)（すべての地形タイプが偶数回）です。

1. チェックポイントに1つ以上立ち寄る場合: 各チェックポイント \(i\) (\(1 \le i \le N\)) からゴール \(N+1\) へ直接移動するコストを足し合わせます。 $\(\min_{1 \le i \le N} (dp[i][K][0] + C_{i, N+1})\)$

2. チェックポイントに1つも立ち寄らない場合 (\(K = 0\) の場合のみ可能): スタートからゴールへ直接移動するコスト \(C_{0, N+1}\) も候補に入ります。

これらの最小値が答えとなります。一度も条件を満たす経路を作れなかった（最小値が \(\infty\) のまま）場合は -1 を出力します。

計算量

時間計算量

• 状態数: \(N \times (K + 1) \times 2^M\)
• 遷移数: 各状態から、次に進むチェックポイント \(next\_i\) の選び方が最大 \(N\) 通り。

したがって、全体の時間計算量は以下のようになります。 $\(O(N^2 \cdot K \cdot 2^M)\)$

最悪ケース（\(K = N \approx 150\), \(M = 8\)）でも、ループ回数は約 \(150^3 \times 2^8 \approx 8.6 \times 10^8\) 回となります。 実装において、不必要な遷移（値が \(\infty\) の状態からの遷移）をスキップする枝刈りを行うことで、実行時間を大幅に削減でき、制限時間内に余裕で間に合わせることができます。

空間計算量

DPテーブルのサイズは \((N+1) \times (K+1) \times 2^M\) です。 $\(O(N \cdot K \cdot 2^M)\)\( \)150 \times 150 \times 256 \approx 5.7 \times 10^6$ 要素の3次元配列となり、メモリ制限に対しても十分に軽量です。

実装のポイント

• ビット演算による高速化: 地形タイプの奇偶の更新は、XOR 演算（^）を用いることで非常に高速に行えます。

• 枝刈り（無駄な遷移のスキップ）: dp[i][j] の中で、値が \(\infty\)（初期値）のままの状態からは遷移を行わないようにします。コード内では active_states をあらかじめ集計して、到達可能な状態からのみ次のループを回すことで、Pythonでも高速に動作させています。

• インデックスの調整: 地形タイプ \(t_i\) は \(1\)-based で与えられるため、ビットシフトで扱いやすいように \(0\)-based（t[i] - 1）に変換しておくと実装がスムーズになります。

  ソースコード

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    M = int(data[1])
    K = int(data[2])

    t = [0] + [int(x) - 1 for x in data[3 : 3 + N]]

    idx = 3 + N
    C = [[0] * (N + 2) for _ in range(N + 1)]
    for i in range(N + 1):
        num_elements = N + 1 - i
        row = [int(x) for x in data[idx : idx + num_elements]]
        idx += num_elements
        for offset, val in enumerate(row):
            C[i][i + 1 + offset] = val

    INF = 10**18

    num_masks = 1 << M
    dp = [[[INF] * num_masks for _ in range(K + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 0

    type_bits = [1 << x for x in t]

    for i in range(N):
        C_i = C[i]
        dp_i = dp[i]
        for j in range(min(i, K) + 1):
            dp_i_j = dp_i[j]
            active_states = [
                (mask, val) for mask, val in enumerate(dp_i_j) if val < INF
            ]
            if not active_states:
                continue

            next_j = min(j + 1, K)
            for next_i in range(i + 1, N + 1):
                cost = C_i[next_i]
                type_bit = type_bits[next_i]
                dp_next = dp[next_i][next_j]
                for mask, dp_val in active_states:
                    val = dp_val + cost
                    n_mask = mask ^ type_bit
                    if val < dp_next[n_mask]:
                        dp_next[n_mask] = val

    ans = INF
    if K == 0:
        ans = min(ans, C[0][N + 1])

    for i in range(1, N + 1):
        cost_to_dest = C[i][N + 1]
        val = dp[i][K][0]
        if val < INF:
            ans = min(ans, val + cost_to_dest)

    if ans >= INF:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    solve()

---

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