Zenn
✨

APC001 C - Vacant Seat解説[python]

2021/01/16に公開
Python
AtCoder
競プロ
二分探索
インタラクティブ
tech

URL

https://atcoder.jp/contests/apc001/tasks/apc001_c

制約

N は奇数
$ 3 <= N <= 99999 $

問題概要

  • 環状にNこの数字が並んでおり、数字は0,1,2のいずれかである。
  • 1と1,2と2が隣り合うことはないとき、Nが奇数なら必ず空席は存在する
  • 高々20回まで指定した場所の数字を見ることができる時、数字が0の場所を当てるプログラムをかけ

提出コード

#!/usr/bin/env python3
import sys


def solve(N: str):
    print(0, flush=True)
    out = input()
    l = 0
    r = int(N)
    l_str = out
    m = int(N)
    flag = 0
    while True:
        if out == "Vacant":
            return
        else:
            if l_str == out:
                flag = 1
            else:
                flag = 0
            if (flag + m - l) % 2 == 0:  # 左側に移動する。
                r = m
                m = (m + l) // 2
            else:  # 右側に移動する
                l = m
                m = (r + m) // 2
                l_str = out
                # print(l, m, "right")
        print(m, flush=True)
        out = input()
    print(l, flush=True)
    if input() == "Vacant":
        return
    print(r, flush=True)
    if input() == "Vacant":
        return
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = next(tokens)  # type: str
    solve(N)


if __name__ == "__main__":
    main()

考察

  • インタラクティブ問題の経験が少なく直感で方針がわかない
  • 制約から二分探索のように絞っていくと予想する
  • 問題の性質を考えると、0は１つだけ存在するわけではないので、"ある区間内に必ず0が１つ以上存在する、しないような区間"を見つけることができると二分探索ができる
    • 0が存在しないような区間では必ず1212..と交互に存在するので"区間長が偶数(4以上)で両端の数字が1と2"、または、"区間長が奇数で両端の数字が1と1or2と2"なら必ず区間内に0が１つ以上存在することがわかる。
    • 初期の探索区間を左端0,右端Nとすると探索区間に必ず0は１つ以上存在するので、
    • 二分探索時には、左端が条件を満たすかだけ判定して、条件を満たすなら r = m, それ以外はl = mにすれば良い

実装方針

  • 条件の判定には　両端の文字が同じかのflagをたて、それと区間の距離の和が2で割り切れるかで判定した。
  • 回数に余裕があるので念のため最後にl,rを両方とも出力するようにした

次回への反省

  • 二分探索を自分で書くのが久しぶりで（bisectを使っていたため）l,rの更新でバグらせてしまった。
  • 二分探索では　m はどちらにせよ更新する、l,rは mが条件を満たすかでどちらを更新するか決まる
  • インタラクティブ問題で、いつ入力を受け取って処理をするコードを書くか迷った。while のはじめに受け取って処理するのが一番直感的

参考

https://qiita.com/mmsstt/items/469a9346ce545709f53c pythonでflush 処理のやり方

Discussion