概要

この問題は、グラフにおける最大重み独立集合問題の変種です。 \(N\) 個の区画を頂点、通路を辺とみなしたとき、隣接する頂点同士を選ばないように頂点集合（倉庫を建てる場所）を選び、その重みの合計（保管量の合計）を最大化します。ただし、合計が \(M\) を超える場合は \(M\) が答えとなります。

考察

1. 問題のモデル化

与えられた制約をグラフ理論の言葉で整理すると以下のようになります。 - 頂点数 \(N \leq 40\) の無向グラフがある。 - 各頂点 \(i\) には重み \(P_i\) が割り当てられている。 - 互いに隣接しない頂点の集合（独立集合）を選び、その重みの総和を最大化する。 - 最終的な答えは \(\min(\text{最大重み}, M)\)。

2. 指数時間アルゴリズムの必要性

最大重み独立集合問題は一般にNP困難な問題であり、効率的な多項式時間アルゴリズムは見つかっていません。 \(N=40\) という制約では、全ての頂点の組み合わせ（\(2^N \approx 10^{12}\)）を試すことは不可能ですが、半分に分ける半分全列挙（Meet-in-the-middle）を用いれば、\(2^{N/2} \approx 2^{20} \approx 10^6\) 程度の計算量で解くことが可能です。

アルゴリズム

1. 半分全列挙の準備

頂点集合を \(N_1 = \{0, \dots, \lfloor N/2 \rfloor - 1\}\) と \(N_2 = \{\lfloor N/2 \rfloor, \dots, N-1\}\) の2つのグループに分けます。

2. 前半部分（\(N_1\)）の処理

\(N_1\) に含まれる頂点のみを使った全ての独立集合を列挙し、それぞれの重みの合計を計算します。 次に、ビットDP（SOS DP: Sum Over Subsets の手法）を用いて、以下の値を計算します。 - dp[mask] = \(N_1\) の部分集合 mask に含まれる頂点のみを使って作れる独立集合の最大重み。

これにより、後ほど「\(N_1\) のうち、この頂点たちは使っても良い」という条件（マスク）が与えられたとき、その範囲内での最大重みを \(O(1)\) で取得できるようになります。

3. 後半部分（\(N_2\)）の処理と結合

\(N_2\) に含まれる頂点のみを使った独立集合を一つずつ列挙します。 ある独立集合 \(S_2 \subseteq N_2\) を選んだとき、これと同時に選ぶことができる \(N_1\) 側の頂点は、「\(S_2\) に含まれるどの頂点とも隣接していない頂点」に限られます。

1. \(S_2\) の重みの合計 \(W_2\) を計算する。
2. \(S_2\) の頂点と隣接している \(N_1\) 側の頂点集合を adj_mask とする。
3. \(N_1\) 側で利用可能な頂点のマスクは valid_mask = all_n1_bits AND NOT adj_mask となる。
4. 全体の重みは \(W_2 + dp[valid\_mask]\) となる。

この値を全ての \(S_2\) について計算し、その最大値を求めます。

計算量

• 時間計算量: \(O(N \cdot 2^{N/2})\)
  • 前半の独立集合列挙とSOS DPに \(O(N \cdot 2^{N/2})\)。
  • 後半の列挙と前半との結合処理に \(O(2^{N/2})\)。
  • \(N=40\) のとき \(2^{20} \approx 10^6\) なので、Pythonでも実行時間制限（5秒）内に十分間に合います。
• 空間計算量: \(O(2^{N/2})\)
  • dp テーブルの保持に \(2^{20}\) 個の要素（数MB〜数十MB程度）を使用します。

実装のポイント

• ビット演算の活用: 隣接行列をビットマスクで管理することで、隣接判定や利用可能頂点の抽出を高速に行えます。

• SOS DP（高速部分集合計算）: dp[mask] を更新する際、各ビットについてループを回すことで、ある集合に含まれる最大値を効率的に伝播させることができます。

• 早期終了: 重みの最大値が既に \(M\) に達した場合は、それ以上探索を続けずに \(M\) を出力して終了することで、実行時間を短縮できます。

• メモリ節約: Pythonの list の代わりに array.array や bytearray を使うことで、メモリ使用量を抑えることができます（今回の制約では必須ではありませんが、より大きな \(N\) では重要になります）。

  ソースコード

import sys
import array

def solve():
    # Read all input at once
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Parse N, M, K
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    # Parse P_i
    P = [int(x) for x in input_data[3:3+N]]
    
    # Build adjacency matrix as bitmasks
    adj = [0] * N
    idx = 3 + N
    for _ in range(K):
        u = int(input_data[idx]) - 1
        v = int(input_data[idx+1]) - 1
        adj[u] |= (1 << v)
        adj[v] |= (1 << u)
        idx += 2
        
    # Split districts into two halves for meet-in-the-middle
    n1 = N // 2
    n2 = N - n1
    
    # Part 1: Compute all independent sets in the first half (N1)
    all_n1 = (1 << n1) - 1
    # dp[mask] will store the maximum weight independent set that is a subset of 'mask'
    dp = array.array('Q', [0] * (1 << n1))
    is_indep1 = bytearray(1 << n1)
    is_indep1[0] = 1 # Empty set is always independent
    
    for i in range(n1):
        bit = 1 << i
        adj_m = adj[i] & (bit - 1)
        p_i = P[i]
        for mask in range(bit):
            if is_indep1[mask] and not (mask & adj_m):
                new_mask = mask | bit
                is_indep1[new_mask] = 1
                dp[new_mask] = dp[mask] + p_i
    
    # SOS DP (Sum Over Subsets) to find the max weight independent set within each mask
    for i in range(n1):
        bit = 1 << i
        for mask in range(0, 1 << n1, bit << 1):
            for x in range(mask, mask + bit):
                if dp[x] > dp[x + bit]:
                    dp[x + bit] = dp[x]
    
    # Current max weight found in N1
    max_w = dp[all_n1]
    if max_w >= M:
        print(M)
        return

    # Part 2: Iterate over independent sets in the second half (N2)
    # and combine them with the best independent set from the first half (N1)
    is_indep2 = bytearray(1 << n2)
    is_indep2[0] = 1
    weight2 = array.array('Q', [0] * (1 << n2))
    adj_to_n1 = array.array('I', [0] * (1 << n2))
    
    for i in range(n2):
        bit = 1 << i
        node_idx = n1 + i
        adj_m_n2 = (adj[node_idx] >> n1) & (bit - 1) # Neighbors in N2 already processed
        adj_m_n1 = adj[node_idx] & all_n1            # Neighbors in N1
        p_val = P[node_idx]
        for mask in range(bit):
            if is_indep2[mask] and not (mask & adj_m_n2):
                new_mask = mask | bit
                is_indep2[new_mask] = 1
                w = weight2[mask] + p_val
                weight2[new_mask] = w
                a = adj_to_n1[mask] | adj_m_n1
                adj_to_n1[new_mask] = a
                
                # Combine current N2 independent set with the best valid N1 independent set
                # Valid N1 nodes are those not adjacent to any node in the N2 set
                res = w + dp[all_n1 & ~a]
                if res > max_w:
                    max_w = res
                    # Early exit if we already reached or exceeded requested amount M
                    if max_w >= M:
                        print(M)
                        return
    
    # Final answer is the minimum of requested total and max capacity found
    print(min(M, max_w))

if __name__ == '__main__':
    solve()

---

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