AtCoder Petrozavodsk Contest 001 C - Vacant Seat (緑色, 500 点)

インタラクティブ...でも問題自体は「単調性が成り立たなくても二分探索できるよ！」という教育的なものだった！

問題へのリンク

問題概要

円形状に並んだ 個の椅子がある ( は奇数)。各椅子は

• 男性がいる
• 女性がいる
• 空席

のいずれかである。どの隣り合う 2 つの席も、同性の人が座っていることはない。また、空席が一つ以上存在することがわかっているのでそれを特定したい。20 回以内の質問で当てよ。

制約

• 

考えたこと

単調でなかったとしても、両端の間に解があることがわかっているときにその間を挟むようにするタイプの二分探索ですね！！！

• 間隔が偶数で、両端の性別が異なる
• 間隔が奇数で、両端の性別が等しい

という場合には、かならずその間に空席が存在することが示せるので、空席を挟むようにして二分探索できる。

#include <bits/stdc++.h>
using namespace std;

bool betemp(string sleft, string sright, int left, int right) {
    if (sleft == sright) return (right - left) % 2 == 1;
    else return (right - left) % 2 == 0;
}

void solve(int N) {
    string vac = "Vacant";
    string sleft, sright, str;
    int left = 0, right = N/2;
    cout << left << endl;
    cin >> sleft;
    if (sleft == vac) return;
    cout << right << endl;
    cin >> sright;
    if (sright == vac) return;

    if (!betemp(sleft, sright, left, right)) {
        swap(sleft, sright), left = right, right = N;
    }
    while (right - left > 1) {
        int mid = (left + right) / 2;
        cout << mid << endl;
        cin >> str;
        if (str == vac) return;
        if (betemp(sleft, str, left, mid)) sright = str, right = mid;
        else sleft = str, left = mid;
    }
}

int main() {
    int N;
    while (cin >> N) solve(N);
}