ABC299 D問題 Find by Query

atcoder.jp

$S_p \ne S_{p+1}$ となる $p$ を一つ求める問題です。
$S_1 \ne S_N$ であることから、 $S_1 = S_2 = \cdots = S_N$ ではなく、どこかで $S_p \ne S_{p+1}$ となります。
1と $N$ の間の $a$ について、 $S_1 = S_a \ne S_N$ であれば、1から $a$ の間に値が変わることが無いかもしれませんが、 $a$ から $N$ の間では少なくとも1つ値が変わるところがあります。そこで、 $a$ から $N$ の間を調べればよいです。 $S_1 \ne S_a = S_N$ であれば、1から $a$ の間を調べればよいです。1と $N$ の中間を $a$ とする二分法を繰り返して範囲を絞り込むことで答えが求められます。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  N = readInt()

  zero = 1
  one  = N

  while one - zero > 1
    a = div( one + zero, 2)
    println("? ",a)
    b = readInt()
    if b == 0
      zero = a
    else
      one = a
    end
  end

  println("! ",zero)

end  # function solve

# main
solve()