ABC190 C - Bowls and Dishes
備忘録
問題
回答
import sys import os import math import bisect import itertools import collections import heapq import queue import array import time # 時々使う # import numpy as np # from decimal import Decimal, ROUND_HALF_UP # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # 再帰の制限設定 sys.setrecursionlimit(10000000) def ii(): return int(sys.stdin.buffer.readline().rstrip()) def il(): return list(map(int, sys.stdin.buffer.readline().split())) def fl(): return list(map(float, sys.stdin.buffer.readline().split())) def iln(n): return [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] def iss(): return sys.stdin.buffer.readline().decode().rstrip() def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split())) def isn(n): return [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] def lcm(x, y): return (x * y) // math.gcd(x, y) MOD = 10 ** 9 + 7 # MOD = 998244353 INF = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N, M = il() AB = [il() for _ in range(M)] K = ii() CD = [il() for _ in range(K)] pattern = [] for i in range(1 << K): dish = [False] * N for j in range(K): c, d = CD[j] if (i >> j) & 1: dish[c-1] = True else: dish[d-1] = True pattern.append(dish) ret = 0 for p in pattern: cnt = 0 for a, b in AB: if p[a-1] and p[b-1]: cnt += 1 ret = max(ret, cnt) print(ret) if __name__ == '__main__': main()
考え方
ボールが置かれるケース数は、
K
人がC
またはD
のどちらか(2通り)にボールを置くため、2 ** K
通りです。
1 <= K <= 16
であることから、全てのケース数を洗い出しても65536
通り程度なので、
bit全探索でボールが置かれる全てのケースを洗い出しました。
あとは洗い出した全てのパターンにおいて、
最もM
個の条件を満たすことができるパターンを探索するだけです。
公式回答にも書かれているとおり、
itertools.product
(デカルト積)を用いると短く記述することができます。
Pythonで複数のリストの直積(デカルト積)を生成するitertools.product | note.nkmk.me
リスト内包表記による、条件を満たした数のカウント方法など、
こういった書き方を息をするようにできるとかっこいいですね。。。