概要

\(N\) 個の宝石から \(K\) 個を選び、円形に並べたときの「輝きの合計 + 隣り合うペアの調和度の合計」を最大化する問題です。これは 重み付きグラフ上で最大重みハミルトン閉路を求める問題 に帰着でき、ビットマスク DP で解きます。

考察

問題の構造を整理する

\(K\) 個の宝石を環状に並べたときの美しさは、次の2つの和です： - 選んだ宝石の輝き \(P\) の合計 - 環状に隣り合う \(K\) 組の調和度 \(C\) の合計

つまり、\(N\) 頂点の完全グラフを考え、辺 \((i, j)\) の重みを \(C_{i,j}\)、頂点 \(i\) の重みを \(P_i\) とすると、\(K\) 頂点の部分集合を選び、その上でハミルトン閉路（すべての頂点をちょうど1回訪問して戻る閉路）を見つけ、頂点重み＋辺重みの合計を最大化する 問題になります。

素朴なアプローチの問題点

\(K\) 個の宝石の選び方は \(\binom{N}{K}\) 通り、それぞれに対して環状の並べ方は \((K-1)!/2\) 通りあります。\(N = 16, K = 16\) の場合、\((16-1)!/2 \approx 6.5 \times 10^{11}\) 通りとなり、全列挙は到底間に合いません。

ビットマスク DP による高速化

ハミルトン閉路問題の定番手法である ビットマスク DP を使います。訪問済みの頂点集合をビットマスクで管理し、「どの頂点集合を訪問済みで、最後にどの頂点にいるか」を状態として DP を行います。

アルゴリズム

1. 起点の固定

環状の並び替えでは回転で同じものを何度も数えてしまいます。これを防ぐため、各部分集合について、最小番号の頂点を起点（パスの始点）に固定 します。こうすると、各ハミルトン閉路を1回だけ数えることになります。

2. DP の定義

\[dp[\text{mask}][v] = \text{maskに含まれる頂点をすべて訪問し、起点から出発して頂点 } v \text{ で終わるパスの辺重みの最大値}\]

ここで mask のビットが立っている頂点が訪問済み頂点集合を表し、起点は mask の最下位ビット（最小番号の頂点）です。

3. 初期化

各頂点 \(v\) に対して、\(dp[1 \ll v][v] = 0\)（頂点 \(v\) だけからなる集合で \(v\) にいる。辺はまだ通っていないので重み \(0\)）。

4. 遷移

mask に含まれる頂点を訪問済みで、現在 \(v\) にいるとき、mask に含まれない頂点 \(u\)（ただし \(u > \text{start}\) を満たすもの）に移動します：

\[dp[\text{mask} \mid (1 \ll u)][u] = \max\left(dp[\text{mask} \mid (1 \ll u)][u],\; dp[\text{mask}][v] + C_{v,u}\right)\]

\(u > \text{start}\) という条件は、起点が常に集合内の最小番号であるという不変条件を保つためです。

5. 閉路の完成

\(|\text{mask}| = K\) となったとき、最後の頂点 \(v\) から起点 start に戻る辺を加えて閉路にします：

\[\text{beauty} = dp[\text{mask}][v] + C_{v,\text{start}} + \sum_{i \in \text{mask}} P_i\]

すべての mask, \(v\) についてこの値の最大値が答えです。

具体例

\(K = 3\)、宝石 \(\{0, 2, 3\}\) を選ぶ場合（0-indexed）： - 起点 = \(0\)（最小番号） - パス例：\(0 \to 2 \to 3\)、辺重み = \(C_{0,2} + C_{2,3}\) - 閉路にする：\(+ C_{3,0}\) - 美しさ：\(P_0 + P_2 + P_3 + C_{0,2} + C_{2,3} + C_{3,0}\)

計算量

• 時間計算量: \(O(2^N \times N^2)\)
  • 各マスク（\(2^N\) 個）について、現在の頂点 \(v\) と次の頂点 \(u\) の組（最大 \(N^2\)）を走査します。実際には mask に含まれる頂点と含まれない頂点のペアなので、もう少し定数は小さくなります。
• 空間計算量: \(O(2^N \times N)\)
  • DP テーブルのサイズです。\(N = 16\) のとき約 \(2^{16} \times 16 = 1{,}048{,}576\) エントリです。

実装のポイント

• 起点の固定: mask & (-mask) でビットマスクの最下位ビットを取得し、それを起点とします。新たに追加する頂点 \(u\) は起点より大きい番号のものに限定することで、同じ閉路を重複して探索しません。

• \(P\) の合計の前計算: sum_P[mask] を前計算しておくと、閉路完成時に \(O(1)\) で輝きの合計を加算できます。

• ビット演算による高速な頂点列挙: tmp = remaining; while tmp: lb = tmp & (-tmp); ... のパターンで、ビットが立っている位置を高速に列挙します。

• \(K = 1, K = 2\) の特殊ケース: \(K = 1\) ではハミルトン閉路の概念が成り立たないため別処理します。\(K = 2\) では2頂点間に2本の辺（往復）があるため \(C_{i,j} + C_{j,i} = 2C_{i,j}\) を加算します。

  ソースコード

import sys
from itertools import combinations

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    P = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    
    C = []
    for i in range(N):
        row = [int(input_data[idx + j]) for j in range(N)]
        C.append(row)
        idx += N
    
    if K == 1:
        print(max(P))
        return
    
    if K == 2:
        best = -float('inf')
        for i in range(N):
            for j in range(i+1, N):
                # In a cycle of 2, there are 2 edges both between i and j
                val = P[i] + P[j] + C[i][j] + C[j][i]
                best = max(best, val)
        print(best)
        return
    
    # For K >= 3, we use bitmask DP for finding the best Hamiltonian cycle on the chosen subset.
    # 
    # Approach: For each subset of size K, find the maximum weight Hamiltonian cycle.
    # We fix one vertex in the subset (the smallest numbered) to avoid counting rotations multiple times,
    # then do DP over bitmask for Hamiltonian path from that vertex, and close the cycle at the end.
    #
    # dp[mask][v] = max sum of edge weights for a path starting at the fixed vertex,
    #               visiting exactly the vertices in mask, ending at v.
    # 
    # Since N <= 16, total states = 2^16 * 16 = ~1M, and for each subset of size K we do work.
    # But actually we can do a single DP over all masks.
    
    # Global DP approach:
    # For any bitmask, we define a "starting vertex" as the lowest-numbered bit in the mask.
    # dp[mask][v] = best path weight from lowest-bit vertex to v, visiting all vertices in mask.
    
    NEG_INF = -float('inf')
    
    # Precompute sum of P for each mask
    sum_P = [0] * (1 << N)
    for mask in range(1, 1 << N):
        lb = mask & (-mask)
        sum_P[mask] = sum_P[mask ^ lb] + P[lb.bit_length() - 1]
    
    # Precompute popcount
    popcount = [0] * (1 << N)
    for mask in range(1, 1 << N):
        popcount[mask] = popcount[mask >> 1] + (mask & 1)
    
    # DP
    # dp[mask][v]: best Hamiltonian path cost (sum of edge weights) from start(mask) to v
    # where start(mask) = lowest set bit of mask, and all bits in mask are visited.
    
    dp = [[NEG_INF] * N for _ in range(1 << N)]
    
    # Initialize: single vertex masks
    for v in range(N):
        dp[1 << v][v] = 0
    
    ans = NEG_INF
    
    for mask in range(1, 1 << N):
        pc = popcount[mask]
        if pc > K:
            continue
        
        start = (mask & (-mask)).bit_length() - 1
        
        for v in range(N):
            if dp[mask][v] == NEG_INF:
                continue
            if not (mask & (1 << v)):
                continue
            
            cur_val = dp[mask][v]
            
            # If we have K vertices, try to close the cycle
            if pc == K:
                cycle_val = cur_val + C[v][start] + sum_P[mask]
                if cycle_val > ans:
                    ans = cycle_val
            else:
                # Extend path: add a new vertex u (u > start to ensure start remains the lowest)
                # Actually, u must not be in mask, and u > start is guaranteed if start is the lowest bit
                # and u is not in mask... not necessarily u > start. But start IS the lowest bit in mask,
                # so any bit not in mask that is < start would become the new lowest bit, breaking our invariant.
                # So we only add u > start.
                remaining = ((1 << N) - 1) & ~mask & ~((1 << (start + 1)) - 1)
                tmp = remaining
                while tmp:
                    lb = tmp & (-tmp)
                    u = lb.bit_length() - 1
                    new_mask = mask | lb
                    new_val = cur_val + C[v][u]
                    if new_val > dp[new_mask][u]:
                        dp[new_mask][u] = new_val
                    tmp ^= lb
    
    print(ans)

solve()

---

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