Codeforces Round #694 (Div. 1) C. Strange Shuffle インタラクティブ問題

単純にインタラクティブ問題のテスト方法が知りたい人は以下を見てください。
【[過去の記事 競技プログラミングのインタラクティブ問題のテストの仕方(mkfifoの利用と出力への色付け)](https://qiita.com/recuraki/items/d4f4c01f588c421c9ced)】
あるいは、以下のコマンドで十分です。

```shell
rm -rf /tmp/fifo &&
 mkfifo /tmp/fifo &&
(python3 1471_e_solver.py < /tmp/fifo) 1>&2  |
 python3 1471_e_interactor.py > /tmp/fifo 1>&2 
```


# はじめに
https://codeforces.com/contest/1470/problem/C


二分探索なインタラクティブ問題です。Interactive問題の解き方は２つです。1.考察によりクエリと答えを想定しコードを書く 2.シミュレータを書いて試行しながら、完成したコードをテストする。

実際のコンテスト中は2の時間はなかなかないかもしれませんが、シミュレータを書いて、あたりをつける＋実際に解くためのシミュレータのコツについて述べます。今回の問題は、大きな入力をシミュレートしようとすると破綻します。そこで、どのように手を抜くかを考えましょう。


# 題意
制約: $ 4\leq n \leq 10^5, 2 \leq k \leq 10^9, kは偶数$
- n個の配列があり、最初、すべての要素は偶数kである。これらは円になっている。つまり、0とn-1はつながっている
- 1単位時間が経過すると、それぞれの要素は「持っている要素の半分(切り上げ)を右の要素に渡し」「持っている要素の半分(切り下げ)を左の要素に渡す」
- これだけであれば、常に各要素の数はkから変わらない
- ただし、この中で、配列のans番目の要素だけは、「持っているすべてを右に渡し」「左には何も渡さない」

この条件において、

- あなたは1000単位時間が与えられ「その瞬間、i番目の要素は何か？」をクエリできる
- ansを求めよ

# シミュレータを書く
まず、愚直にシミュレーションするコードを書きます。最初のn,k,ansで適当な数を与えて、"? q"と"! ans"することができます。途中経過を見るために、stderrでdebug文字列を表示します。

```Python
import sys, math
n,k,ans = 8,4,4
l = [k] * n
qcount = -1
print(n, k)
while qcount < 1000:
    print("turn{0}: before {1}".format(qcount, l), file=sys.stderr)
    qcount += 1
    s = input()
    if s[0] == "!":
        if int(s.split(" ")[1]) == ans: print("OK!"), sys.exit(0)
        else: print("NG!"), sys.exit(20)
    print(l[int(s.split()[1]) - 1])
    ll = [0] * n
    for ii in range(n):
        lsend = math.floor(l[ii] / 2)
        rsend = math.ceil(l[ii] / 2)
        lnum = ii - 1 if ii!=0 else n-1
        rnum = ii + 1 if ii!=(n-1) else 0
        if (ans-1) == ii:
            ll[rnum] += l[ii]
            continue
        ll[lnum] += lsend
        ll[rnum] += rsend
    l = ll
print("GAMEOVER!")
sys.exit(10)
```
このコードを書いたうえで走らせ、何度かクエリを投げます。すると、以下のように遷移することがわかります。

```text
# 奇数個(7,4,4)
turn-1: before[4, 4, 4, 4, 4, 4, 4]
turn0: before [4, 4, 2, 4, 6, 4, 4]
turn1: before [4, 3, 2, 4, 6, 5, 4]
turn2: before [3, 3, 2, 4, 6, 5, 5]
turn3: before [4, 3, 2, 4, 6, 5, 4]
turn4: before [3, 3, 2, 4, 6, 5, 5]
turn5: before [4, 3, 2, 4, 6, 5, 4]

# 偶数個(8,4,4)
turn-1: before[4, 4, 4, 4, 4, 4, 4, 4]
turn0: before [4, 4, 2, 4, 6, 4, 4, 4]
turn1: before [4, 3, 2, 4, 6, 5, 4, 4]
turn2: before [3, 3, 2, 4, 6, 5, 5, 4]
turn3: before [3, 3, 2, 4, 6, 5, 5, 4]
turn4: before [3, 3, 2, 4, 6, 5, 5, 4]
turn5: before [3, 3, 2, 4, 6, 5, 5, 4]
```

こういった場合、偶数と奇数で結果が異なる気がしたので、偶奇のパラメータを試します。どうやら以下のことがわかります。

- ansを中心に右は1要素ずつ数が増え、左は1要素ずつ数が減る(これを浸食と呼びます)
- この要素は右と左がつながっており、右と左の浸食がぶつかると、奇数個の場合はその要素同士が時折kに戻る(偶奇ごと)。偶数の場合はある１つがkになる(このあたりを境界、と以下で呼びます)

# 解き方を考える

1000回のクエリで$ 4\leq n \leq 10^5 $の中からansを探すので、乱択、二分探索、線形探索のようなキーワードが思い浮かびます。今回は線形探索を考えます。

最大の要素数を考えます。単純に$10^5$の要素を探索するのは無理なので、例えば、100ずつインクリメントしてスキャンすれば、1000回で100刻みの要素をスキャンできますが、例えば、ans=50だったら、1,2ターン目にいきなり0,100と要素をスキップしてしまいます。ただし、990回目すぎに900個程度左に減った数が侵食しているため、それを気が付くことができます。

ここで、最初にある特定のポインタを調べ続けて510回待つことにします。すると、ansから左右510個、つまり、1020個の要素は値がkから変化しています。そこで、今度は、500ずつインクリメントし、スキャンしてみましょう。たかだか200回以内でスキャンは終了し、この中で必ず値の変化が気が付きます。すでに500回以上侵食されているので、その変化点より右にansがあるのは自明です。そして、+1000した要素より左にansがあることも自明です。これで区間が絞れたので二分探索をします。midがkより小さいなら、より左にあり、大きいなら右にある、という二分探索を行えばよいです。

<font color=red>以下、追加されたテストケースでコーナーケースであることに気が付いたのですが、</font>kを引き当てた場合、それが正解とは限らないことです。上記を見ると、境界を引き当ててしまった場合、それはansではないことがわかります。
ansを引き当てた場合、偶然kを引き当てた場合の区別はつかないので、その左右を確認し、左が小さく、右が大きいかを確認する必要があります。
もし、計算によりansを求めることも可能ですし、二分探索のポインタを適切に戻してやることで再度、正しい区間での二分探索ができます。(今回のソルバでは二分探索のポインタを戻しています)

尚、最初の510回待っている最中に、そのポインタに値の変化があった場合、大きくなるか、小さくなるかで、待ったターン分右か左かを即座に判断することが可能です。

# 実装の上でのポイント
上記を実装するの自身は難しくないですが、配列の左右がつながっていたり、1-originであったりするので、注意しましょう。

ポイントは、この配列を「長さnでansの位置に題意の挙動をする印が付いている無限の配列」としてに扱うと楽です。つまり、正しい配列長さに合わせて計算をするのではなく、余りを使って考えると、nが小さい時の二分探索も考えやすいです。具体的には以下ののようにしてやります。

```Python
        mid = (l + r) // 2
        print("?", mid % n + 1)
```

# シミュレータの実装(大きな数字対応版)
最初にシミュレータを書きましたが、毎単位時間$10^5$の配列をシミュレーションすると時間がかかります。(計算できる時間ですが、500クエリ待ったりするので遅いです)
ので、手抜きをします。ソルバを考えると、要は、

- n個の配列で初期値k。tターン目は、ansからt離れたところまで、「左は小さく」「右は大きく」値を返す。つまり、適当に、k-1とk+1を返せばよい
- ただし、kがぶつかるときのシミュレーションはしっかりと行う

とすればいいです

```Python
import sys
import math
#n, k = 2*10**4, 1000
#ans = 701
#n,k,ans= 10000, 10, 700
#n,k,ans=100000,100,80116
#n,k,ans = 4,2,1
n,k,ans = 7, 4, 4
l = [k] * n
qcount = -1
print(n, k)
while qcount < 1000:
    qcount += 1
    s = input()
    #print("recv raw:", s, file=sys.stderr)
    if s[0] == "!":
        if int(s.split(" ")[1]) == ans: print("OK!"), sys.exit(0)
        else: print("NG!"), sys.exit(20)
    qnum = int(s.split()[1])
    if ans == qnum:
        print(k)
        continue
    if n & 1 == 0 and qnum == ( ((ans-1) + (n//2)) % n + 1): # boarder
        print(k)
        continue
    if n & 1 == 1 and qnum == ( ((ans-1) + (n//2)) % n + 1) and qcount >= (n//2) and qcount%2 == 0: # boarder
        print(k)
        continue
    if n & 1 == 1 and qnum == ( ((ans-1) + (n//2) + 1) % n + 1) and qcount >= (n//2) and qcount%2 == 0: # boarder
        print(k)
        continue
    if ans-qcount <= qnum < ans:
        print(k-1)
        continue
    if ans < qnum <= ans+qcount:
        print(k+1)
        continue
    if (ans + qcount) > n:
        if qnum <= (ans + qcount - n + 1):
            print(k + 1)
            continue
    print(k)
    continue
print("GAMEOVER!")
sys.exit(10)
```

# テストする
後述するソルバーを

```shell
rm -rf /tmp/fifo &&
 mkfifo /tmp/fifo &&
(python3 1471_e_solver.py < /tmp/fifo) 1>&2  |
 python3 1471_e_interactor.py > /tmp/fifo 1>&2 
```
で走らせます。この辺りのコマンドは、
[過去の記事 競技プログラミングのインタラクティブ問題のテストの仕方(mkfifoの利用と出力への色付け)](https://qiita.com/recuraki/items/d4f4c01f588c421c9ced)を見てください。

```
(略)
? 1
8
? 2
7
? 10
9
! 6
OK!
```

できた！

# 実装(ソルバー)

```Python
"""
rm /tmp/fifo && mkfifo /tmp/fifo && (python3 1471_e.py < /tmp/fifo)1>&2  | python3 1471_e_interactor.py > /tmp/fifo1>&2
"""
import sys
n, k = map(int, input().split())
def do():
    for i in range(502):
        print("? 1")
        sys.stdout.flush()
        res = int(input())
        if res == k: continue
        if res < k: # is left
            res =  i
            res %= n
            print("!", res + 1)
            sys.stdout.flush()
            return
        if res > k:
            res = -i
            res %= n
            print("!", res + 1)
            sys.stdout.flush()
            return
    if n < 500:
        print("?", (0 + 1) % n + 1)
        resr = int(input())
        print("?", (0 - 1) % n + 1)
        resl = int(input())
        if (resl < k < resr):
            print("!",  1)
            return
        else:
            print("!", n//2 + 1)
            return
    for i in range(400):
        cur = 1 + 500*i
        print("?", cur)
        sys.stdout.flush()
        res = int(input())
        if res == k: continue # cannot judge
        if res < k: # more right
            l = cur
            r = cur + 510+500
            break
        if res > k: # more left
            l = cur - 501
            r = cur
            break
    # start Nibutan
    while l <= r:
        mid = (l + r) // 2
        print("{0} {1}=> mid={2}".format(l, r, mid), file=sys.stderr)
        print("?", mid % n + 1)
        sys.stdout.flush()
        res = int(input())
        if res == k:
            print("?", (mid+1) % n + 1)
            resr = int(input())
            print("?", (mid-1) % n + 1)
            resl = int(input())
            if not (resl < k < resr):
                l -= 501*2
                continue
            print("!", mid % n + 1)
            sys.stdout.flush()
            return
        if res < k: # more right
            l = mid + 1
            continue
        if res > k: # more left
            r = mid - 1
            continue
    print("?", l)
    sys.stdout.flush()
    res = int(input())
    if res == k:
        print("!", l)
        sys.stdout.flush()
        return
    print("?", r)
    res = int(input())
    if res == k:
        print("!", r)
        sys.stdout.flush()
        return
    print("cannot!!!")


sys.stdout.flush()

do()
```
https://codeforces.com/contest/1470/submission/104201603