概要

チェックポイントを番号の昇順に選び、各地形タイプの訪問回数がすべて偶数になるようにしつつ、訪問数が \(K\) 個以上である経路の最小コストを求めます。

地形タイプ数 \(M\) が小さいため、各タイプの訪問回数の偶奇をビットマスクで管理する DP を行います。

考察

まず、立ち寄るチェックポイントの集合をそのまま全探索すると、候補は最大で \(2^N\) 通りあります。
\(N \leq 150\) なのでこれは不可能です。

一方で、移動は常に番号が増加する方向のみです。
つまり、現在最後にいる地点が分かっていれば、次に選べるチェックポイントはそれより大きい番号のものだけです。

また、各地形タイプについて必要なのは「何個選んだか」そのものではなく、「偶数個か奇数個か」だけです。
地形タイプ数は \(M \leq 8\) と小さいので、偶奇状態を \(M\) ビットの整数で表せます。

例えば \(M=3\) のとき、

• 地形タイプ \(1\) の訪問回数が奇数なら下から \(1\) ビット目が \(1\)
• 地形タイプ \(2\) の訪問回数が奇数なら下から \(2\) ビット目が \(1\)
• 地形タイプ \(3\) の訪問回数が奇数なら下から \(3\) ビット目が \(1\)

とします。

すべてのタイプの訪問回数が偶数である状態は、ビットマスクが \(0\) の状態です。

チェックポイント \(i\) を訪問すると、その地形タイプ \(t_i\) の偶奇が反転します。
これはビット演算で

\(mask \oplus (1 << (t_i - 1))\)

と表せます。

したがって、

• これまでに選んだチェックポイント数
• 最後にいる地点
• 各地形タイプの偶奇状態

を持つ DP をすればよいです。

アルゴリズム

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

\(dp_c[j][mask]\) を、

• ちょうど \(c\) 個のチェックポイントを訪問済み
• 最後にいるチェックポイントが \(j\)
• 地形タイプの偶奇状態が \(mask\)

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

ただし、\(c=0\) のときだけ \(j=0\)、つまり麓にいる状態を考えます。

初期状態は

\(dp_0[0][0] = 0\)

です。

現在地点を \(j\)、次に訪問するチェックポイントを \(i\) とします。
移動は番号が増加する方向だけなので、\(j < i \leq N\) です。

チェックポイント \(i\) を訪問すると、偶奇状態は

\(newmask = mask \oplus typebit_i\)

に変わります。

遷移は次のようになります。

\(dp_{c+1}[i][newmask] = \min(dp_{c+1}[i][newmask],\ dp_c[j][mask] + C_{j,i})\)

ここで、\(typebit_i = 1 << (t_i - 1)\) です。

各 \(c\) について DP を更新したあと、もし \(c \geq K\) かつ \(mask = 0\) なら、地形バランス条件を満たしています。
その状態から山頂 \(N+1\) へ直接移動するコストを足して答えを更新します。

つまり、候補は

\(dp_c[j][0] + C_{j,N+1}\)

です。

また、\(K=0\) の場合は、チェックポイントを一切訪問せずに

\(0 \to N+1\)

と直接移動することも可能なので、初期解として \(C_{0,N+1}\) を考えます。

最終的に答えが更新されていなければ、条件を満たす経路は存在しないので \(-1\) を出力します。

計算量

• 時間計算量: \(O(N^3 \cdot 2^M)\)
• 空間計算量: \(O(N^2 + N \cdot 2^M)\)

\(O(N^2)\) は移動コスト \(C_{a,b}\) の保存に使います。
DP は「現在の訪問数」と「次の訪問数」だけ持てばよいので、\(O(N \cdot 2^M)\) に抑えられます。

実装のポイント

地形タイプの偶奇はビットマスクで管理します。

typ[i] = 1 << (t_i - 1)

チェックポイント \(i\) を訪問するときは、対応するビットを XOR で反転します。

new_mask = mask ^ typ[i]

また、すべての地形タイプの訪問回数が偶数なら、合計訪問数も必ず偶数です。
そのため、コードでは訪問数が奇数のときは答え候補の確認を省略しています。

if newcnt >= K and (newcnt & 1) == 0:

DP 配列全体を毎回すべて走査すると無駄が多いため、コードでは active に「到達可能なマスク」だけを記録しています。
これにより、実行時間を定数倍で削減しています。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    pos = 0
    N = data[pos]
    M = data[pos + 1]
    K = data[pos + 2]
    pos += 3

    typ = [0] * (N + 1)
    for i in range(1, N + 1):
        typ[i] = 1 << (data[pos] - 1)
        pos += 1

    C = [[0] * (N + 2) for _ in range(N + 1)]
    for a in range(N + 1):
        row = C[a]
        for b in range(a + 1, N + 2):
            row[b] = data[pos]
            pos += 1

    S = 1 << M
    INF = 10 ** 30
    end = N + 1
    N1 = N + 1

    dp = [[INF] * S for _ in range(N + 1)]
    active = [[] for _ in range(N + 1)]
    dp[0][0] = 0
    active[0].append(0)

    ans = C[0][end] if K == 0 else INF

    for cnt in range(N):
        ndp = [[INF] * S for _ in range(N + 1)]
        nactive = [[] for _ in range(N + 1)]

        for j in range(cnt, N):
            am = active[j]
            if not am:
                continue

            rowdp = dp[j]
            crow = C[j]

            if len(am) == 1:
                m = am[0]
                base = rowdp[m]
                for i in range(j + 1, N1):
                    d = m ^ typ[i]
                    nr = ndp[i]
                    nv = base + crow[i]
                    if nv < nr[d]:
                        if nr[d] == INF:
                            nactive[i].append(d)
                        nr[d] = nv
            else:
                for i in range(j + 1, N1):
                    add = crow[i]
                    bit = typ[i]
                    nr = ndp[i]
                    na = nactive[i]
                    for m in am:
                        d = m ^ bit
                        nv = rowdp[m] + add
                        if nv < nr[d]:
                            if nr[d] == INF:
                                na.append(d)
                            nr[d] = nv

        newcnt = cnt + 1
        if newcnt >= K and (newcnt & 1) == 0:
            best = ans
            for i in range(newcnt, N1):
                v = ndp[i][0]
                if v < INF:
                    total = v + C[i][end]
                    if total < best:
                        best = total
            ans = best

        dp = ndp
        active = nactive

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

if __name__ == "__main__":
    main()

---

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