DDCC2020予選: E - Majority of Balls

問題概要

個のボールがあり，個は赤色で個は青色である。

個 のボールのうちの個を指定してその個のボールのうちどちらの色の方が多いか，という質問を 回まですることができる。

このとき， 個のボールの色をすべて当てよ。

(問題文は https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_e に記載されている。)

制約

• 
• は奇数
• 回まで質問ができる

アイディア

とする。

ここで とすると，ボールの個のボールでも色のボールが多いことになってしまうので矛盾する。よって である。

このことから，となるがに存在する(もしに対してであるとするととなりと矛盾)。

このとき，なので，とするとに含まれる色のボールの個数は以上以下であり，よってに含まれる色のボールの個数は以上以下となる(ボールが色ならば色のボールの個数はつ増え，それ以外の場合は変わらないため)。

次に，とすると(ただしはではない方の色)とすると，に含まれる色のボールの個数は以上以下となるので，に含まれる色のボールの個数は以上以下となる(ボールが色ならば色のボールの個数はつ増え，それ以外の場合は変わらないため)。

以上から，に含まれる色のボールの個数は以上以下となり，つまりに含まれるのボールの個数は個，よって区間]のボールは赤色と青色のボールを同数含む。

区間]は両色のボールを同数ずつ含むので，この区間内のボールに関しては自身を除いた個のボールをそれぞれ質問で投げればよい。

さらに，とのボールの色は違うので(同じであればとなるので矛盾)，] ]についても両色のボールを同数ずつ含むといえるので，この区間内のボールに関しても自身を除いた個のボールをそれぞれ質問で投げればよい。

これが基本方針である。

高速化

となる を探すところで二分法を使えばこの部分での質問は回程度におさまり，全体的な質問回数が回程度となる。

実装

素直に実装するだけ。

コード

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

int N,RB='R'+'B';

string reply;
char getreply(){
    cin >> reply;
    return reply[0];
}

void sendquestion(int s){
    int i;
    cout << "?";
    for(i=0; i<N; ++i){
        cout << " " << s+i;
    }
    cout << endl; cout.flush();
}

char c,ans[225];

int main(void){
    int i,j,p,l,r,m;
    cin >> N;
    l = 1; r = N+1;
    sendquestion(1); c = getreply();
    while(r-l>1){
        m = (l+r)/2;
        sendquestion(m);
        if(c == getreply()){
            l = m;
        }else{
            r = m;
        }
    }
    p = l;
    for(i=p; i<=p+N; ++i){
        cout << "?";
        for(j=p; j<=p+N; ++j){
            if(i==j){
                continue;
            }
            cout << " " << j;
        }
        cout << endl; cout.flush();
        ans[i-1] = RB-getreply();
    }
    for(i=1; i<=N*2; ++i){
        if(p<=i && i<=p+N){
            continue;
        }
        cout << "?";
        for(j=1; j<=p; ++j){
            if(i==j){
                continue;
            }
            cout << " " << j;
        }
        for(j=p+N; j<=N*2; ++j){
            if(i==j){
                continue;
            }
            cout << " " << j;
        }
        cout << endl; cout.flush();
        ans[i-1] = RB-getreply();
    }
    cout << "! ";
    for(i=0; i<N*2; ++i){
        cout << ans[i];
    }
    cout << endl; cout.flush();
    return 0;
}

(提出したものはこちら)

感想

橙パフォうれしい