DISCO ディスカバリーチャンネル 2020 予選 E - Majority of Balls (橙色, 800 点)

の場合の場合分け中で出力時に "! " を入れるのを忘れていることにずっと気づかずに WA Rush という...ひどい......コンテスト本番じゃなくてよかった。。。

問題へのリンク

問題概要 (インタラクティブ)

を奇数とする。 個のボール があって、そのうちの 個が青く、 個が赤い。それぞれの index のボールが青いか赤いかわからない。

いま、以下のような質問を繰り返すことで、 個それぞれのボールの色を当てたい。

• 個のボールのうちの 個を選んで、問いかける
• その中で赤の方が多ければ Red と返り、青の方が多ければ Blue と返ってくる

210 回まで質問することができる。すべてのボールの色を当てて出力せよ。

制約

• 

考えたこと

こういうのはまずは小さな から試して様子を見るのがいいんだと思う。まず の場合は、

• 「1」と聞いて Red だったら、答えは "RB"
• 「1」と聞いて Blue だったら、答えは "BR"

ということがわかる。1 回の質問で当てられる。 のときは、

• ひとまず (1, 2, 3) と聞いてみる。答えが Red として一般性を失わない。
• 次に 1 個ずらして (1, 2, 4) と聞いてみたくなる。このとき...

もしこのとき答えが Blue だったならば、実は

• 3 は Red
• 4 は Blue

ということが確定する。なぜならば、もし 3 が Blue であったら 1, 2 はともに Red でなければならないが、このとき 1, 2, 4 が Blue になることはありえない。

より一般に以下のことがいえる

---

質問 A と質問 B とで、 個が共通しているとする。

• 質問 A が共通分とボール a からなっていて、返答が Red
• 質問 B が共通分とボール b からなっていて、返答が Blue

という状況であったならば、a は Red で b は Blue である。さらに言えば共通分の 個のうち、ちょうと半数が Red で、半数が ちょうど Blue である。

---

なぜなら、a が Blue だとすると、共通部分の N-1 個のうち、[tex: \frac{N-1}{2} + 1} 個が Red でなければならないが、この時点で質問 B の答えは Red になってしまう。よって a は Red であり、同様に b は Blue である。

そして

• 質問 A の状況から、 個のうち 個以上が Red でなければならない
• 質問 B の状況から、 個のうち 個以上が Blue でなければならならい

ということがわかるので、 個のうちのちょうど半数が Red で、ちょうど半数が Blue であることもわかる。

そういう状況を作る

以上から、 個が共通している質問のペアであって、一方が Red でもう一方が Blue になるようなものを作れたら強い。たとえば のとき

• (1, 2, 3, 4, 5) と (6, 7, 8, 9, 10) は、一方が Red でもう一方が Blue である

という状態になっていることに着目する。ここでは仮に (1, 2, 3, 4, 5) が Red であるとする。このとき

• 1, 2, 3, 4, 5： Red
• 2, 3, 4, 5, 6
• 3, 4, 5, 6, 7
• 4, 5, 6, 7, 8
• 5, 6, 7, 8, 9
• 6, 7, 8, 9, 10： Blue

という風に上から下へと見ていったときに、どこかに Red から Blue へと変わる境目があるはずである！！！これを二分探索で見つけられる。

見つけたら

ひとたび、 個が共通していて答えが異なるペアを見つけたら、その 個は赤と青の個数が等しいことに着目しよう。たとえば で の赤と青が等しかったとしよう。そうしたら単純に各 に対して、

• () が Red なら は Red
• () が Blue なら は Blue

ということがわかる。 の場合についてもあとから同じようにする。

回数

以上の方法だと、

• 二分探索で 回
• その後、各ボールを判定するのに 回

となる。 として、ちょうど 210 回にギリギリおさまる感じになる！！！

#include <iostream>
#include <vector>
#include <set>
using namespace std;

// Input
int N;

// question (v[0], v[1], v[2], ...)
string get(const vector<int> &v) {
    cout << "?";
    for (auto vi : v) cout << " " << vi+1;
    cout << endl;
    string res;
    cin >> res;
    return res;
}

// question (f, f+1, f+2, ...)
string get(int f) {
    vector<int> v(N);
    for (int i = 0; i < N; ++i) v[i] = f + i;
    return get(v);
}

int main() {
    cin >> N;
    if (N == 1) {
        auto tmp = get(0);
        if (tmp == "Red") cout << "! RB" << endl;
        else cout << "! BR" << endl;
        return 0;
    }

    // search change point by binary search
    int left = 0, right = N;
    string start = get(left);
    while (right - left > 1) {
        int mid = (left + right) / 2;
        if (get(mid) == start) left = mid;
        else right = mid;
    }
    vector<int> base(N-1), nbase;
    for (int i = 0; i < N-1; ++i) base[i] = left + i+1;

    // phase 1
    int blue = 0, red = 0;
    string res(N*2, 'U');
    for (int i = 0; i < N*2; ++i) {
        if (i >= base[0] && i <= base.back()) continue;
        base.push_back(i);
        auto tmp = get(base);
        if (tmp == "-1") return 0;
        if (tmp == "Red") {
            res[i] = 'R';
            if (red < N/2) ++red, nbase.push_back(i);
        }
        else {
            res[i] = 'B';
            if (blue < N/2) ++blue, nbase.push_back(i);
        }
        base.pop_back();
    }

    // phase 2
    for (auto i : base) {
        nbase.push_back(i);
        auto tmp = get(nbase);
        if (tmp == "-1") return 0;
        if (tmp == "Red") res[i] = 'R';
        else res[i] = 'B';
        nbase.pop_back();
    }
    cout << "! " << res << endl;
    return 0;
}