概要

地点 \(0\) から地点 \(N+1\) まで、番号が増加する順にチェックポイントを経由しながら移動するとき、「立ち寄る個数が \(K\) 個以上」かつ「各地形タイプごとに立ち寄る個数が偶数」という条件を満たしつつ、消費体力（経路上のコスト総和）を最小化する問題です。

考察

まず、移動が「常に番号が増加する方向」にのみ進むことに注目します。これは、地点を頂点とした DAG（有向非巡回グラフ）上の最短経路問題 とみなせます。地点 \(a\) から地点 \(b\)（\(a < b\)）へコスト \(C_{a,b}\) の辺が張られていると考えればよいです。

しかし、単純な最短経路ではなく、次の \(2\) つの追加条件があります。

1. 個数の条件: 立ち寄るチェックポイント数 \(s \geq K\)
2. 地形バランスの条件: 各地形タイプ \(j\) について、立ち寄ったチェックポイントのうちタイプ \(j\) の個数が偶数

これらの条件を「経路を進む途中の状態」として持ちながら最短経路を求める必要があります。そこで 動的計画法（DP） を用います。

状態として何を持つか

ポイントは、条件を判定するのに必要な情報を「コンパクト」に表現することです。

• 個数の条件: 立ち寄った個数そのものは最大 \(N\) まで増えますが、必要なのは「\(K\) 個以上かどうか」だけです。よって個数は \(K\) で頭打ちにして \(\min(\text{個数}, K)\) として持てば十分です。これにより状態数を \(0 \sim K\) の \(K+1\) 通りに抑えられます。
• 地形バランスの条件: 各タイプの個数の偶奇だけが問題になります。タイプは \(M\) 種類（\(M \leq 8\)）なので、各タイプの偶奇を \(M\) ビットの ビットマスク で表現できます。あるタイプのチェックポイントに立ち寄るたびに、対応するビットを反転（XOR）させればよいです。最終的にマスクが \(0\)（全タイプ偶数）であれば条件を満たします。

このように「個数は \(K\) で頭打ち」「偶奇はビットマスク」という工夫により、状態数を有限かつ小さく抑えられるのが本問の核心です。

アルゴリズム

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

\[dp[i][c][mask] = \text{現在地点 } i \text{ にいて、立ち寄った個数が } \min(\cdot, K) = c\text{、各タイプの偶奇が } mask \text{ であるときの最小コスト}\]

• 初期状態: \(dp[0][0][0] = 0\)（麓からスタート、何も立ち寄っていない）
• 遷移: 地点 \(i\) から次に立ち寄るチェックポイント \(j\)（\(i < j \leq N\)）を選び、
  • 新しい個数 \(nc = \min(c+1, K)\)
  • 新しいマスク \(nm = mask \oplus (1 \ll (t_j - 1))\)
  • \(dp[j][nc][nm] \leftarrow \min(dp[j][nc][nm],\ dp[i][c][mask] + C_{i,j})\)
• 終了: 地点 \(i\) から山頂 \(N+1\) へ直接移動する。ただし条件を満たす必要があるため、\(c \geq K\) かつ \(mask = 0\) のときのみ、答えの候補 \(dp[i][c][mask] + C_{i,N+1}\) を計上する。

地点番号が増加する方向のみに遷移するので、\(i\) を \(0\) から順に処理すれば自然に DP のトポロジカル順序が保たれ、ループ一回で計算できます。

すべての候補の中での最小値が答えです。条件を満たす経路が存在しない場合（候補が一つもない場合）は \(-1\) を出力します。

計算量

状態数は \(O(N \cdot K \cdot 2^M)\)、各状態からの遷移先が \(O(N)\) あるので、

• 時間計算量: \(O(N^2 \cdot K \cdot 2^M)\)（最悪 \(K = N\) で \(O(N^3 \cdot 2^M)\)）
• 空間計算量: \(O(N \cdot K \cdot 2^M)\)

制約に \(N^3 \cdot 2^M \leq 3 \times 10^8\) とある通り、この計算量で十分高速に動作します。

実装のポイント

• 個数の頭打ち: nc = min(c+1, K) とすることで、\(K\) 以上はすべて同一状態として扱います。これを忘れると状態数が爆発し、また「\(K\) 以上」の判定が正しく行えません。

• 偶奇のビット反転: タイプ \(t_j\) に立ち寄ると mask ^= (1 << (t_j - 1)) で偶奇を切り替えます。タイプ番号は \(1\) 始まりなので、ビット位置は \(t_j - 1\) になる点に注意します。

• 多次元配列の平坦化: コードでは \(dp[i][c][mask]\) を idx(i,c,mask) = (i*(K+1)+c)*2^M + mask という式で \(1\) 次元配列にまとめています。これにより、メモリ確保とアクセスを効率化しています。

• INF の扱い: コストは最大 \(10^9\)、経路長は最大 \(N+1\) 程度なので総和が \(32\) ビット整数を超えるため、long long を用います。INF は十分大きな値（\(4 \times 10^{18}\)）に設定し、未到達状態を表します。

• \(s=0\) のケース: どこにも立ち寄らず麓から山頂へ直接移動する場合も、\(dp[0][0][0]\) から \(N+1\) への遷移として自然に扱えます（ただし \(K = 0\) のときのみ条件を満たします）。

  ソースコード

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

int main(){
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    vector<int> t(N+1);
    for(int i=1;i<=N;i++) scanf("%d", &t[i]);
    
    static long long C[152][152];
    for(int s=0;s<=N;s++){
        for(int b=s+1;b<=N+1;b++){
            long long x; scanf("%lld",&x);
            C[s][b]=x;
        }
    }
    
    const long long INF = (long long)4e18;
    int MASK = 1<<M;
    // dp[i][c][mask], i in 0..N
    // flatten
    int Kp = K+1;
    auto idx=[&](int i,int c,int mask)->long long{
        return ((long long)i*Kp + c)*MASK + mask;
    };
    long long total = (long long)(N+1)*Kp*MASK;
    vector<long long> dp(total, INF);
    
    dp[idx(0,0,0)] = 0;
    
    long long ans = INF;
    
    for(int i=0;i<=N;i++){
        for(int c=0;c<Kp;c++){
            for(int mask=0;mask<MASK;mask++){
                long long cur = dp[idx(i,c,mask)];
                if(cur==INF) continue;
                // go to N+1
                if(c>=K && mask==0){
                    long long v = cur + C[i][N+1];
                    if(v<ans) ans=v;
                }
                // go to checkpoint j
                for(int j=i+1;j<=N;j++){
                    int nc = min(c+1, K);
                    int nm = mask ^ (1<<(t[j]-1));
                    long long v = cur + C[i][j];
                    long long &ref = dp[idx(j,nc,nm)];
                    if(v<ref) ref=v;
                }
            }
        }
    }
    
    if(ans==INF) printf("-1\n");
    else printf("%lld\n", ans);
    return 0;
}

---

この解説は claude4.8opus-high によって生成されました。