E - 倉庫の配置計画 / Warehouse Placement Plan Editorial by admin Editorial for printing
Claude 4.6 Opus (Thinking)概要
グラフ上で隣接する2頂点を同時に選ばない（独立集合）という制約のもと、選んだ頂点の重みの合計を最大化する問題です。ただし合計は \(M\) を超えられません。\(N \leq 40\) という制約に対し、半分全列挙（Meet in the Middle）と部分集合に対するmax のSOS DPを組み合わせて解きます。
考察
問題の本質
この問題は最大重み独立集合問題に帰着できます。区画をグラフの頂点、通路を辺とみなし、隣接する2頂点を同時に選ばないように頂点を選び、選んだ頂点の重み（\(P_i\)）の合計の \(\min(\text{合計}, M)\) を最大化します。
素朴なアプローチ
全ての頂点の部分集合 \(2^N\) 通りを列挙し、独立集合かどうか判定して最大重みを求める方法が考えられます。しかし \(N \leq 40\) の場合、\(2^{40} \approx 10^{12}\) 通りとなり、到底間に合いません。
\(N \leq 20\) なら？
\(2^{20} \approx 10^6\) 通りなので全列挙が可能です。これがヒントとなり、\(N\) を半分に分けて Meet in the Middle を適用するアイデアに至ります。
半分に分けた後の結合の課題
前半の独立集合と後半の独立集合を組み合わせるとき、以下の条件が必要です：
- 前半だけで独立集合であること
- 後半だけで独立集合であること
- 前半の頂点と後半の頂点の間に辺がないこと（cross edge の制約）
条件3を効率的に処理するために、前半の独立集合ごとに「後半のどの頂点が使えなくなるか（blocked mask）」を計算し、後半の独立集合と整合するかを判定します。
blocked mask による結合
- 前半の独立集合を選ぶと、それらの頂点から後半への辺が伸びているため、後半の一部の頂点が使えなくなります。これをblocked mask（ビットマスク）で表現します。
- 後半で選んだ頂点集合を \(s_2\) とすると、\(\text{blocked} \cap s_2 = \emptyset\)（blocked が \(s_2\) の補集合の部分集合）である必要があります。
- 後半の各独立集合 \(s_2\) に対し、\(\overline{s_2}\)（\(s_2\) の補集合）の全ての部分集合の中で、前半の最大重みを高速に求められれば良いです。
これは SOS（Sum/Max over Subsets）DP で前処理できます。
アルゴリズム
ステップ1: 前半の列挙
頂点を前半（\(0, 1, \ldots, \lfloor N/2 \rfloor - 1\)）と後半（\(\lfloor N/2 \rfloor, \ldots, N-1\)）に分割します。
前半の全部分集合 \(2^{\lfloor N/2 \rfloor}\) 通りを列挙し、独立集合であるものについて： - 重みの合計 \(w_1\) を計算 - 後半に対する blocked mask \(b\) を計算（前半の選んだ頂点から後半への辺の OR） - \(\text{best\_first}[b] = \max(\text{best\_first}[b],\, w_1)\) と更新
ステップ2: SOS DP（部分集合 max）
\(\text{best\_first}[b]\) に対し、「\(b\) の全ての部分集合での最大値」が \(\text{best\_first}[b]\) に入るように更新します。
具体的には各ビット \(j\) について： $\(\text{best\_first}[b] \leftarrow \max(\text{best\_first}[b],\, \text{best\_first}[b \oplus (1 \ll j)]) \quad (\text{if } b \text{ の第 } j \text{ ビットが 1})\)$
これにより、\(\text{best\_first}[s]\) は「blocked mask が \(s\) の部分集合であるような前半独立集合の最大重み」を表します。
ステップ3: 後半の列挙と結合
後半の全部分集合 \(2^{\lceil N/2 \rceil}\) 通りを列挙し、独立集合であるものについて： - 重みの合計 \(w_2\) を計算 - available mask \(= \overline{s_2}\)（後半のうち \(s_2\) に含まれないビット）を計算 - \(\text{best\_first}[\text{available}]\) を参照（これが条件を満たす前半の最大重み \(w_1\)） - \(\text{ans} = \max(\text{ans},\, \min(w_1 + w_2,\, M))\) と更新
具体例
\(N = 4,\, M = 100,\, P = [30, 40, 50, 20]\) で辺が \((1,2)\) のみの場合：
- 前半: 頂点 \(\{0, 1\}\)、後半: 頂点 \(\{2, 3\}\)
- 辺 \((0, 1)\) は前半内にあるので、前半では \(\{0\}\) か \(\{1\}\) か \(\emptyset\) のみが独立集合
- 後半の各独立集合と組み合わせ、合計が最大かつ \(M\) 以下のものを選ぶ
計算量
\(h_1 = \lfloor N/2 \rfloor,\; h_2 = \lceil N/2 \rceil\) とします（いずれも最大20）。
- 時間計算量: \(O(2^{h_1} \cdot h_1 + 2^{h_2} \cdot h_2 + 2^{h_2} \cdot h_2)\)
- 前半列挙: \(O(2^{h_1} \cdot h_1)\)
- SOS DP: \(O(2^{h_2} \cdot h_2)\)
- 後半列挙+結合: \(O(2^{h_2} \cdot h_2)\)
- 全体で \(O(N \cdot 2^{N/2})\) 程度
- 空間計算量: \(O(2^{h_2})\)（\(\text{best\_first}\) テーブル）
\(N = 40\) のとき \(2^{20} \approx 10^6\) 程度で十分高速です。
実装のポイント
隣接関係のビットマスク管理: 各頂点 \(i\) の隣接頂点を
adj[i]としてビットマスクで持つと、mask & adj[i]で独立集合の判定が高速にできます。独立集合の判定の高速化: 各頂点を追加するとき、既に選ばれたより小さい番号の頂点との隣接のみチェックすることで、重複判定を避けます（
adj[i] & ((1 << i) - 1) & mask）。SOS DP の方向: 今回は「部分集合の max」を求めるため、ビットが立っているところから立っていないところへ伝播させます。これにより、クエリ時は \(O(1)\) で最大値を取得できます。
\(M\) の上限制約: 合計が \(M\) を超えないように
min(total, M)を取ることを忘れないようにします。ソースコード
import sys
from itertools import combinations
def solve():
input_data = sys.stdin.buffer.read().split()
idx = 0
N = int(input_data[idx]); idx += 1
M = int(input_data[idx]); idx += 1
K = int(input_data[idx]); idx += 1
P = [0] * N
for i in range(N):
P[i] = int(input_data[idx]); idx += 1
# adjacency as bitmask
adj = [0] * N
for _ in range(K):
u = int(input_data[idx]) - 1; idx += 1
v = int(input_data[idx]) - 1; idx += 1
adj[u] |= (1 << v)
adj[v] |= (1 << u)
# Maximum weight independent set with N <= 40
# Use meet-in-the-middle approach
if N <= 20:
# Simple bitmask enumeration
best = 0
for mask in range(1 << N):
# Check if independent set
valid = True
total = 0
for i in range(N):
if mask & (1 << i):
if mask & adj[i]:
valid = False
break
total += P[i]
if valid:
best = max(best, min(total, M))
print(best)
return
# Meet in the middle for N <= 40
# Split into two halves
half1 = N // 2
half2 = N - half1
# For each subset of the first half that is independent,
# record which vertices in the second half are still available
# and the total weight
# Enumerate all independent sets in the first half
# For each, compute: weight and "blocked" mask in second half
# First half: vertices 0..half1-1
# Second half: vertices half1..N-1
# For second half, adj restricted to second half vertices
# adj2[i] for i in second half = adj[half1+i] restricted to second half bits
# We need to group first-half results by the "available mask" in the second half
# Then for each group, we want the maximum weight from first half
# Then enumerate independent sets in available vertices of second half
# But the number of distinct "available masks" could be up to 2^half2 which is 2^20 = 1M
# And for each we enumerate subsets... that's too much directly
# Alternative: enumerate both halves independently, then combine
# For first half: enumerate all independent sets, store (blocked_mask_in_half2, weight)
# For second half: enumerate all independent sets, store (mask_in_half2, weight)
# Combine: for each second half IS with mask s2, we need first half IS whose blocked_mask & s2 == 0
# blocked_mask = union of adj[i] & half2_bits for i in first half IS
# Group first half by blocked_mask, keep max weight for each blocked_mask
# Then for each second half IS (s2, w2), iterate over all blocked_masks that are subsets of complement of s2
# Use SOS (sum over subsets) - actually we need max over subsets
# We'll use "max over supersets" DP
# For first half: best_first[blocked] = max weight of first half IS with that blocked mask
# Then do a "superset max" relaxation: for each blocked mask b,
# best_first[b] = max over all b' where b' is superset of b of best_first[b']
# Wait, we want: given available = complement of s2, find max best_first[b] where b is subset of available_complement...
# Actually: we need blocked & s2 == 0, i.e., blocked is subset of ~s2
# So for a given s2, we want max of best_first[b] over b subset of (~s2 & half2_fullmask)
# This is "max over subsets" which can be done with SOS in O(2^half2 * half2)
h2_full = (1 << half2) - 1
best_first = [-1] * (1 << half2)
for mask in range(1 << half1):
valid = True
total = 0
blocked = 0
bits = mask
while bits:
i = (bits & -bits).bit_length() - 1
if mask & adj[i] & ((1 << half1) - 1) & ((1 << (i)) - 1): # check lower bits only to avoid double
valid = False
break
total += P[i]
blocked |= (adj[i] >> half1) & h2_full
bits &= bits - 1
if not valid:
continue
if total > best_first[blocked]:
best_first[blocked] = total
# SOS max over subsets: best_first[b] = max over all b' subset of b
# We want for query s: max best_first[b] for b subset of s
# Standard SOS: iterate bits, for each bit, propagate from subset to superset
for bit in range(half2):
for b in range(1 << half2):
if b & (1 << bit):
sub = b ^ (1 << bit)
if best_first[sub] > best_first[b]:
best_first[b] = best_first[sub]
ans = 0
for mask2 in range(1 << half2):
valid = True
total2 = 0
for j in range(half2):
if mask2 & (1 << j):
real_j = half1 + j
local_adj = (adj[real_j] >> half1) & h2_full
if mask2 & local_adj & ((1 << j) - 1):
valid = False
break
total2 += P[real_j]
if not valid:
continue
avail = h2_full ^ mask2 # bits not in mask2 (but we need complement of mask2 for blocked constraint)
# We need blocked subset of ~mask2 in half2 bits = avail
w1 = best_first[avail]
if w1 < 0:
continue
val = min(total2 + w1, M)
if val > ans:
ans = val
print(ans)
solve()
この解説は claude4.6opus-thinking によって生成されました。
posted:
last update: