DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選 E - Majority of Balls

問題ページ
と にクエリを飛ばしてRBと返ってきた場合，『x 「n-1個』 y」 で２つの区間でRBの数の変動に影響するのはxとyの高々2個しかない．n-1個の部分でRとBの数が異なる場合は不可能．よって の範囲内にはRBが 個ずつ存在する．

このような範囲 + 1個 に対してクエリを投げると，クエリの答えが追加した1個の色と一致する．2n個全てについて，このようなクエリを投げると全てのボールの色を特定できる．

あとは210-99*2=12回で上述したRBが反転するような場所を見つけられればよい．これは にRとBを両方含むようにしながら，範囲を狭めていく二分探索を行えばよい． は 8 程度なので問題ない．

わかってたこと

• RとBを 個ずつ見つけられれば嬉しい
• 長さ の区間を 個全部試したら2点は確定しそう

わかるべきだったこと

• RB が連続している部分が必ず存在し，その部分にRBの数が等しい区間が存在する
  多分これがわかれば 回は思いついたはず
• RBが切り替わる点を一点見つける → 単調性はないが二分探索でできる
• この制約なら10回あれば くらいの操作はできる
  10回が適当なおまけで 回のクエリにするのだと思ってしまった

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
ll col[200] = {0, 1, 0, 1, 1, 0};  
string query(vector<ll> v) {  
#ifdef DEBUG_  
    cout << "?";  
    for(auto i: v) cout << " " << i+1;  
    cout << endl;  
  
    ll cnt0 = 0, cnt1 = 0;  
    for(auto i: v) {  
        if(col[i] == 0) cnt0++;  
        else cnt1++;  
    }  
    string ret;  
    if(cnt0 > cnt1) ret = "Red";  
    else ret = "Blue";  
    cout << ret << endl;  
    return ret;  
#else  
    cout << "?";  
    for(auto i: v) cout << " " << i+1;  
    cout << endl;  
  
    string ret;  
    cin >> ret;  
    return ret;  
#endif  
}  
  
int main(void) {  
    ll n;  
    cin >> n;  
  
    string ls, rs;  
    {   
        vector<ll> v(n);  
        iota(ALL(v), 0);  
        ls = query(v);  
        if(ls == "Red") rs = "Blue";  
        else rs = "Red";  
    }  
  
    ll lb=0, ub=n;  
    while(ub-lb>1) {  
        ll mid = (lb+ub)/2;  
        vector<ll> v;  
        FOR(i, mid, mid+n) v.push_back(i);  
        if(query(v) == ls) lb = mid;  
        else ub = mid;  
    }  
    dump(lb, ub);  
  
    // [ub, ub+n-1) が RB均等  
    vector<ll> r, b;  
    string ans(2*n, '?');  
    REP(i, ub) {  
        vector<ll> v;  
        FOR(j, ub, ub+n-1) v.push_back(j);  
        v.push_back(i);  
  
        string ret = query(v);  
        if(ret == "Red") ans[i] = 'R', r.push_back(i);  
        else ans[i] = 'B', b.push_back(i);  
    }  
    FOR(i, ub+n-1, 2*n) {  
        vector<ll> v;  
        FOR(j, ub, ub+n-1) v.push_back(j);  
        v.push_back(i);  
  
        string ret = query(v);  
        if(ret == "Red") ans[i] = 'R', r.push_back(i);  
        else ans[i] = 'B', b.push_back(i);  
    }  
      
    FOR(i, ub, ub+n-1) {  
        vector<ll> v;  
        REP(j, (n-1)/2) v.push_back(r[j]);  
        REP(j, (n-1)/2) v.push_back(b[j]);  
        v.push_back(i);  
  
        string ret = query(v);  
        if(ret == "Red") ans[i] = 'R';  
        else ans[i] = 'B';  
    }  
  
    cout << "! " << ans << endl;  
  
    return 0;  
}