ABC015 C - 高橋くんのバグ探し
備忘録
問題
回答
import sys import os import math import bisect import itertools import collections import heapq import queue import array # 時々使う # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # from decimal import Decimal # from collections import defaultdict, deque # 再帰の制限設定 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 INF = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N, K = il() T = [il() for _ in range(N)] for prod in list(itertools.product(*T)): ret = 0 for p in prod: ret ^= p if ret == 0: print('Found') exit() else: print('Nothing') if __name__ == '__main__': main()
考え方
取りうる全てのパターンを探索する全探索の問題です。
本回答ではデカルト積を用いて、全探索を行なっています。
- 回答概要
- 「ユーザの回答」の全パターンを探索する
- 「ユーザの回答」の全パターンの探索にはデカルト積を用いる
ケース数が少ないため、全探索による回答を考えます。
この問題では「ユーザの回答」で発生しうる全てのパターンを生成します。
「ユーザの回答」の全てのパターンの生成にはデカルト積(itertools.product
)を使用します。
数学において、集合のデカルト積(デカルトせき、英: Cartesian product)または直積(ちょくせき、英: direct product)、直積集合、または単に積(せき、英: product)、積集合は、集合の集まり(集合族)に対して各集合から一つずつ元をとりだして組にしたもの(元の族)を元として持つ新たな集合である。 Wikipedia - 直積集合
1つの質問を1つの集合と考え、選択肢のデカルト積を求めることによって、全てのパターンを網羅することが可能です。
あとは、生成した集合のXOR
を求めて、条件に一致するか否かの判定を行います。