けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

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

問題へのリンク

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

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

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

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

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

制約

  •  1 \le N \le 99

考えたこと

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

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

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

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

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

  • 3 は Red
  • 4 は Blue

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

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


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

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

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


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

そして

  • 質問 A の状況から、 N-1 個のうち  \frac{N-1}{2} 個以上が Red でなければならない
  • 質問 B の状況から、 N-1 個のうち  \frac{N-1}{2} 個以上が Blue でなければならならい

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

そういう状況を作る

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

  • (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 へと変わる境目があるはずである!!!これを二分探索で見つけられる。

見つけたら

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

  • ( 4, 5, 6, 7, i) が Red なら  i は Red
  • ( 4, 5, 6, 7, i) が Blue なら  i は Blue

ということがわかる。 i = 4, 5, 6, 7 の場合についてもあとから同じようにする。

回数

以上の方法だと、

  • 二分探索で  O(\log{N})
  • その後、各ボールを判定するのに  2N

となる。 N = 99 として、ちょうど 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;
}