Edit

【pythonでABC190を解説】C - Bowls and Dishes

問題概要

問題ページ

C - Bowls and Dishes
C - Bowls and Dishes

問題ページへ移動する

問題文

\(1, 2, \dots, N\) の番号がついた \(N\) 個の皿と、\(1, 2, \dots, M\) の番号がついた \(M\) 個の条件があります。
条件 \(i\) は、皿 \(A_i\) と皿 \(B_i\) の両方にボールが (\(1\) 個以上) 置かれているとき満たされます。
\(1, 2, \dots, K\) の番号がついた \(K\) 人の人がいて、人 \(i\) は皿 \(C_i\) か皿 \(D_i\) のどちらか一方にボールを置きます。
満たされる条件の個数は最大でいくつでしょうか？

制約

  • 入力は全て整数
  • \(2 ≤ N ≤ 100\)
  • \(1 ≤ M ≤ 100\)
  • \(1 ≤ A_i < B_i ≤ N\)
  • \(1 ≤ K ≤ 16\)
  • \(1 ≤ C_i < D_i ≤ N\)

問題の考察

ACコード

import sys
import itertools


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    ab = [list(map(int, input().rstrip('\n').split())) for _ in range(m)]
    k = int(input().rstrip('\n'))
    cd = [list(map(int, input().rstrip('\n').split())) for _ in range(k)]
    mx = 0
    for it_v in itertools.product(range(2), repeat=k):
        ls = [0] * n
        for i, v in enumerate(it_v):
            ls[cd[i][v]-1] = 1
        cnt = 0
        for a, b in ab:
            if ls[a-1] == 1 and ls[b-1] == 1:
                cnt += 1
        mx = max(mx, cnt)
    print(mx)


if __name__ == '__main__':
    solve()

-Edit
-