【今日の精進】ARC078E - Awkward Response

毎日格上の問題を倒すやつの63日目です。

問題リンク

atcoder.jp

問題概要

すぬけくんのお気に入りの整数 が隠されてるよ。

以下のような受け答えをするすぬけくんに最大 回質問して、 を特定してね。

• 「 はお気に入りの整数か?」と聞かれたとき
  • と の辞書順の大小と数としての大小が一致するときY
  • でなければN

解法

まず桁数を特定します。そうすると辞書順が単調になってわかりやすいです。

そのために、 の冪乗について質問します。

このとき、 が の冪乗でなければ、桁数を完璧に特定できます。

が の倍数の時は少し厄介ですが、 の冪乗に1を足したもので質問すると良いです。

あとはにぶたんで終わりですが、聞きたい数の 倍を聞くとしっかりと単調になります。

提出コード

from random import randint
class Judge:
    def __init__(self,N=None):
        self.N=N
        if self.N is None:
            self.N=randint(1,10**9)
        self.cnt=0
    
    def ques(self,n):
        print("?",n,flush=True)
        self.cnt+=1
        assert 1<=n<=10**18
        assert self.cnt<=64
        return input()
        if n>self.N and str(n)>str(self.N):
            return "Y"
        elif n<=self.N and str(n)<=str(self.N):
            return "Y"
        return "N"
    
    def answer(self,n):
        print("!",n,flush=True)
        assert n==self.N
        exit()
T=1
for _ in range(T):
    J=Judge()
    if J.ques(10**10)=="Y":
        ans=1
        for i in range(9,0,-1):
            if J.ques(10**(i-1)+1)=="N":
                ans=10**i
                break
        J.answer(ans)
        continue
    ok=-1
    ng=-1
    for i in range(8,-1,-1):
        if J.ques(10**i)=="Y":
            ok=10**i
            ng=10**(i+1)
            break
    while ng-ok>1:
        mid=(ok+ng)//2
        if J.ques(mid*10)=="N":
            ok=mid
        else:
            ng=mid
    J.answer(ng)

Submission #47811995 - AtCoder Regular Contest 078

感想

おもしろいなぁ