u++の備忘録

ABC015「C - 高橋くんのバグ探し」をPythonで解く

python 競プロ

ABC014「C - 高橋くんのバグ探し」をPythonで解いた。

atcoder.jp

愚直に全通りをfor文で回す解答もあるが、競技プログラミングをPythonで解く上で、より汎用的な解法に落とし込めたので、まとめておく。

解答

import itertools
from functools import reduce
from operator import xor


N, K = list(map(int, input().split()))

T = []
for i in range(N):
	T.append(list(map(int, input().split())))

ans = 'Nothing'

for pr in list(itertools.product(*T)):
	if not (reduce(xor, pr)):
		ans = 'Found'

print(ans)

解説

  • 何かと便利な itertools を使って全通りを列挙
  • 今回興味があるのは組み合わせ一つに対応する真偽値なので reduce を使う

itertools

  • 直積を計算してくれる itertools.product() を使う
  • 多重リストの前に * を付けるとアンパックされる
print(T)
print(*T)

[[1, 3, 5, 17], [2, 4, 2, 3], [1, 3, 2, 9]]
[1, 3, 5, 17] [2, 4, 2, 3] [1, 3, 2, 9]

qiita.com

reduce