コンテンツにスキップ

SamCoding Round 7 (Div. 2) J - Lying Guard

サイト
SamCoding
コンテスト
SamCoding Round 7 (Div. 2)
問題
J - Lying Guard(常設版)

11 以上 NN 以下の秘密の数 TT を当てるインタラクティブ問題です(N≤1018N \le 10^{18})。? i と質問すると、TT と ii の大小関係が >、<、= のいずれかで返ってきます。

ただし、答える番人はゲーム全体を通して 1 回だけ 嘘をつくことがあります。= の答えが嘘のこともあります。質問は 190190 回までです。

ふつうの二分探索で、同じ質問を 3 回ずつして多数決をとります。

嘘はゲーム全体で高々 1 回なので、同じ質問への 3 回の答えのうち、少なくとも 2 回は本当です。そのため、多数決をとれば必ず正しい答えが得られます。正しい答えだけで二分探索を進めれば、ふつうの二分探索と同じく TT が求まります。

範囲 [l,r][l, r] の真ん中 mm を聞き、> なら l=m+1l = m + 1、< なら r=m−1r = m - 1、= ならそこで終わりにします。範囲の大きさは 1 回ごとに半分以下になるので、繰り返しは ⌊log⁡21018⌋+1=60\lfloor \log_2 10^{18} \rfloor + 1 = 60 回以下です。1 回につき 3 回質問するので、合計 180180 回以下で、上限の 190190 回に収まります。

Python
from collections import Counter
N = int(input())
l = 1
r = N
while 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 - 1
print("!", l, flush=True)

3 回の答えを Counter で数え、most_common()[0][0] で最も多い答えを取り出しています。= のときは l = r = m としてループを抜けます。