概要

\(N(\le 16)\) 個の宝石からちょうど \(K\) 個を選び、円環状に並べたときの「頂点重み \(P_i\) + 隣接辺重み \(C_{i,j}\)」の合計を最大化します。
これは「長さ \(K\) の重み付きサイクル（巡回順序）の最大化」を bit DP で解きます。

考察

重要な気づき

• 美しさは
  • 選んだ宝石の輝き和 \(\sum P_i\)
  • 円環で隣り合う \(K\) 本の辺の調和度和 \(\sum C_{i,j}\) の合計です。
• 「どの \(K\) 個を選ぶか」と「その \(K\) 個をどう並べるか」が同時に絡むため、単純に
  • \(K\) 個の選び方：\({N \choose K}\)
  • 並べ方：\((K-1)!/2\)（回転・反転同一を除く） を全探索すると最大で \({16 \choose 8}\cdot 7! \approx 6.5\times 10^7\) を超え、辺の加算もあるので現実的ではありません。

対策：bit DP（巡回セールスマン型）

• 「ある集合を使って、ある頂点で終わる最良値」を状態にする bit DP を使うと、
  • 集合の増やし方（遷移）が \(2^N\) 個程度に抑えられ、
  • 並べ方（順序）の最適化も DP が吸収してくれます。
• ただし、始点を固定して通常の TSP DP をすると「その始点を含む集合」しか扱えません。
  そこで本コードでは 選んだ集合の最小番号を始点に固定する ことで、全ての \(K\) 個集合を漏れなく 1 回ずつ扱います。

具体的には、任意の選ばれた集合 \(S\) には最小要素 \(s=\min S\) が必ず存在するので、 - \(s\) を始点に固定 - \(s\) 以上の頂点だけを対象にして DP とすれば、その集合はちょうどその \(s\) の回でのみ登場します（重複しない）。

アルゴリズム

以下では、ある \(s\) を「選ぶ集合の最小番号（=始点）」として固定して考えます。

状態

\(s,s+1,\dots,N-1\) の \(m=N-s\) 個をローカルに \(0,1,\dots,m-1\) に詰め直します（ローカル 0 が始点 \(s\)）。

• \(dp[\text{mask}][u]\)：
  • ローカル頂点集合 mask（必ず bit0 を含む）を使い、
  • 始点 0 から始めて、最後が \(u\) で終わる パス を作ったときの最大値
  • 値の中身は
    \(\sum P(\text{使った頂点}) + \sum C(\text{パス上の隣接辺})\)

初期値： - \(dp[1<<0][0] = P_0\)（始点のみ）

遷移（パスを 1 頂点伸ばす）

mask の末尾が \(u\) のとき、まだ使っていない頂点 \(v\) を末尾に追加して

[ dp[mask\cup{v}][v] = \max\Big(dp[mask][u] + C_{u,v} + P_v\Big) ]

（頂点 \(v\) を追加するので \(P_v\)、辺 \((u,v)\) を追加するので \(C_{u,v}\) を足す）

長さが \(K\) になったらサイクルに閉じる

使った頂点数が \(K\) になった状態 mask では、末尾 \(u\) から始点 0 に戻す辺を足して円環にします：

[ \text{beauty} = dp[mask][u] + C_{u,0} ]

これで「\(K\) 個を円環に並べた美しさ」になり、最大値 ans を更新します。

全体

• \(s=0,1,\dots,N-1\) を全て試す（ただし \(N-s \ge K\) のときだけ）
• 各 \(s\) について上の DP を行い、ans の最大を答えとして出力します。

計算量

• 時間計算量: \(O(N^2 2^N)\)
  （各 \(s\) で \(O(m^2 2^m)\) 程度、\(N\le16\) なので十分間に合います）
• 空間計算量: \(O(N 2^N)\)
  （最大で \((1<<N)\times N\) 程度の DP 配列）

実装のポイント

• 「最小要素を始点に固定」するために、各 \(s\) 回では頂点集合を \([s,N)\) に制限し、さらに mask は常に bit0 を含むように range(1, size, 2)（下位 bit が 1 のみ）で回しています。

• 値が負になり得るので、DP 初期値は十分小さい NEG=-10^18 を使います。

• popcount（集合サイズ）を事前計算しておき、\(K\) を超える mask を早めに枝刈りします。

• ビット走査（b = x & -x）で「集合中の要素列挙」「未使用要素列挙」を高速に行っています。

  ソースコード

import sys
from array import array

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    K = next(it)
    P = [next(it) for _ in range(N)]
    C = [[next(it) for _ in range(N)] for _ in range(N)]

    maxmask = 1 << N

    pc = [0] * maxmask
    for m in range(1, maxmask):
        pc[m] = pc[m >> 1] + (m & 1)

    bit_index = [-1] * maxmask
    for i in range(N):
        bit_index[1 << i] = i

    NEG = -10**18
    ans = NEG

    for s in range(N):
        m = N - s
        if m < K:
            continue

        verts = list(range(s, N))
        Psub = [P[v] for v in verts]
        Csub = [[C[vi][vj] for vj in verts] for vi in verts]

        size = 1 << m
        fullmask = size - 1
        dp = array('q', [NEG]) * (size * m)

        dp[m + 0] = Psub[0]  # mask=1, end=0

        for mask in range(1, size, 2):  # must include start (bit0)
            cnt = pc[mask]
            if cnt > K:
                continue
            base = mask * m

            sub = mask
            while sub:
                bit = sub & -sub
                u = bit_index[bit]
                sub -= bit

                val = dp[base + u]
                if val == NEG:
                    continue

                if cnt == K:
                    total = val + Csub[u][0]
                    if total > ans:
                        ans = total
                    continue

                rem = fullmask ^ mask
                while rem:
                    b = rem & -rem
                    v = bit_index[b]
                    rem -= b

                    newmask = mask | b
                    idx = newmask * m + v
                    cand = val + Csub[u][v] + Psub[v]
                    if cand > dp[idx]:
                        dp[idx] = cand

    print(ans)

if __name__ == "__main__":
    main()

---

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