SamCoding Round 7 (Div. 2) J - Lying Guard
- サイト
- SamCoding
- コンテスト
- SamCoding Round 7 (Div. 2)
- 問題
- J - Lying Guard(常設版)
以上 以下の秘密の数 を当てるインタラクティブ問題です()。? i と質問すると、 と の大小関係が >、<、= のいずれかで返ってきます。
ただし、答える番人はゲーム全体を通して 1 回だけ 嘘をつくことがあります。= の答えが嘘のこともあります。質問は 回までです。
ふつうの二分探索で、同じ質問を 3 回ずつして多数決をとります。
嘘はゲーム全体で高々 1 回なので、同じ質問への 3 回の答えのうち、少なくとも 2 回は本当です。そのため、多数決をとれば必ず正しい答えが得られます。正しい答えだけで二分探索を進めれば、ふつうの二分探索と同じく が求まります。
範囲 の真ん中 を聞き、> なら 、< なら 、= ならそこで終わりにします。範囲の大きさは 1 回ごとに半分以下になるので、繰り返しは 回以下です。1 回につき 3 回質問するので、合計 回以下で、上限の 回に収まります。
Python
from collections import Counter
N = int(input())l = 1r = Nwhile l < r: m = (l + r) // 2 c = Counter() for _ in range(3): print("?", m, flush=True) c[input()] += 1 k = c.most_common()[0][0] if k == "=": l = r = m elif k == ">": l = m + 1 else: r = m - 1print("!", l, flush=True)3 回の答えを Counter で数え、most_common()[0][0] で最も多い答えを取り出しています。= のときは l = r = m としてループを抜けます。