AtCoder Petrozavodsk Contest 001 C - Vacant Seat

問題
提出コード

解法

インタラクティブ問題なので、二分探索を考えていきます。
まずは、どこか1つの席の情報がわかっていないと何も始まらないので、番の席を特定します。
ここが空席ならばその時点で終了、女性だったならば、男性だった場合と真逆のことをかんがえればよいので、男性だった場合について考えていきます。
番目が男性だった場合、番、番…の席に、男女交互に配置すると下の図のようになります。

ここで、青が男性、橙が女性を表します。
このままだと、図のようにと番目の席に座る人が、どちらも男性になってしまいます。
なので、これを回避するために、の区間のどこかしらに、空席が存在しているはずです。

次に、番の席の情報を特定したとします。空席ならばその時点で操作が終わるので、それ以外について考えます。
上の図で割り振った男女男女…は、席の番号が偶数ならば男性、奇数ならば女性になっているはずです。
番目の情報は、この偶奇に対する男女と一致しているか、していないかの2択です。

• 一致している(が奇数ならば男性、偶数ならば女性)場合
  この場合、からまでの席は、 空席が1つもなく、男女交互に座っている、もしくは空席が存在している、の2パターン存在しています。
  つまり、この部分は、空席が存在していない可能性があるので、この区間を今後探索するのは効率が悪そうです。
  一方、からまでの席は、最初の状況と同じで、もし仮に以降も男女交互で並んでいるとすると、と番目の席について矛盾が生じます。
  ということは、少なくとも1つはこの部分に空席が存在しているはずです。

だった場合

よって、結局はについて、同じ探索を行えばよさそうです。

• 一致してない(が奇数ならば女性、偶数ならば男性)場合
  このパターンは先ほどと逆の状況になります。
  からの区間は、男女交互に配置しても条件を満たすことができるため、空席が存在するかもしれませんし、存在しないかもしれません。
  逆に、からの部分については、男女交互に配置すると矛盾が生じるので、空席が確実に1つは存在します。

よって、こちらのパターンについては、について同じ探索を行えばよさそうです。

上の状況を、どちらのパターンにころんでも効率よく行うために、を区間のちょうど真ん中にしてあげるとよいです。ということで、結果二分探索を行えばよいことになります。
結局、やることは

1. 番の席について調べる。調べるべき区間をとする。

2. について調べる。についてクエリを出して、その部分が、仮にから男女交互に配置していった場合の情報と一致するかどうかを調べる。一致したら、次に調べる区間をとし、そうでなければとする。空席が見つかるまでこれを繰り返す

ということを行えばよいです。

感想

久々のインタラクティブ問題でした。AtCoderだと初めてかもしれないです。
あんまり経験がないので、インタラクティブといえば二分探索っぽいことをしたくなります。そこから考察をさらっと終わらせたのはよかったのですが、例によってデバッグで時間をかけました。
xorを利用して条件の一致を判定したので、その部分を丁寧にやる必要がありましたね…