APC001 - C - Vacant Seat

にぶたんをスラスラ書けるようになりたい。

この問題でAtCoder Problems の BootCamp for Beginners 完埋めです～！ 初のインタラクティブ問題だった。

問題

atcoder.jp

考えたこと

男性と女性が隣り合っちゃいけないので、男女男女男女…と並べればいいけれど、椅子は奇数個なのでどこかで隣り合っちゃう。 椅子の番号のodd/evenでの性別を帰るためには空席を挟む必要がある。

はじめに０番目の椅子に座ってる性別をチェックして、二分探索しながら検索範囲を狭めていけば、20回以内に終わらせることができる。

範囲を狭めた結果、クエリを投げる椅子の偶奇が変わっちゃうことがあるので注意した。

解答

にぶたんの基本的な書き方を整理しといたほうがいい気がした。

#include <bits/stdc++.h>

using namespace std;

#define rep(i,n)      for(long long(i)=0;(i)<(n);(i)++)
#define kiriage(a,b)  ((a)+(b)-1)/(b)

int main(){

    long n;
    cin >> n;

    string ret, top_sex;
    long lhs = 0;
    long rhs = n - 1;
    long cur = (rhs + lhs) / 2;

    // 0の位置がなにか調べる
    cout << 0 << endl;
    cin >> ret;
    if(ret == "Vacant"){
        return 0;
    }

    top_sex = ret;

    do{
        // query 送出
        cout << cur << endl;

        // ans get
        cin >> ret;

        if(ret == "Vacant"){
            return 0;
        } else {
            bool flg1 = ( cur & 0x01 ) == 0;
            bool flg2 = ret == top_sex;

            if(flg1 & flg2 || !flg1 && !flg2){
                lhs = cur;
                cur = kiriage((rhs - lhs), 2) + lhs;
            } else {
                rhs = cur - 1;
                cur = kiriage((rhs - lhs), 2) + lhs;
            }
        }
    } while(1);

    return 0;
}

学んだこと

にぶたんで検索範囲は左端は範囲外にしとくといいらしい。←もう少し勉強しましょう。

感想

BootCampの最終問題だったので緊張しました。

終わってみるとあっけないような気持ち。これからはCのやってないの解いたり、Recommend解いたりしていくかな。