AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

Donutsプロコンチャレンジ2015 B - Tokyo 7th シスターズ

問題原文

atcoder.jp

解法

なんかすごそう。
入力がとてもとてもめんどくさそう。

少し落ち着いて見ると、   {}_{16} C_9 × M ≒ 6 × 10^{5} 程度なので全部試せることがわかる。

実装

from itertools import combinations
N, M = map(int, input().split())
A = list(map(int, input().split()))
B, P = [], []
for i in range(M):
    row = list(map(int, input().split()))
    B.append(row[0])
    P.append(set([r - 1 for r in row[2:]]))

ans = 0
for select in combinations(range(N), 9):
    select = set(list(select))
    tmp_ans = 0
    tmp_ans += sum([A[s] for s in select])
    for b, p in zip(B, P):
        if len(p & select) >= 3:
            tmp_ans += b
    ans = max(ans, tmp_ans)

print(ans)

感想

試験管水が解けなくて逃げてきたのだけどこれも水diffゥ!!