Educational Codeforces Round 87 G: Find a Gift

こういうの典型なんですかね？結構面白い気がしたのでブログに残しておく

問題概要

$N$ 個の箱が一列に並んでいる。箱の中身は石またはギフトである。石が入っている箱はすべて同じ重さであり、ギフトが入っているどの箱よりも真に重い。ギフトが入っている箱どうしは重さが異なる可能性がある (注意: 石が入っている箱より軽いことは保証される)

高々 50 回、以下の形式の質問をすることで、最も左に位置する、ギフトが入っている箱の番号 を当てよ。

積集合が空 (つまりお互いに要素に被りがない) であるような、空でない添字集合 $A, B$ をジャッジに投げて質問する。これは、「 $A$ に属する箱の重さの総和と、 $B$ に属する箱の重さの総和を比較したときに、どちらが重いか (どちらも同じであるばあいは同じであること) 」を質問しており、ジャッジからはその回答が得られる。

解説

※この解説は公式の解説をベースに書いています。

最も左に位置するものを当てる必要があるので、左に位置する箱から順に情報が得られるのが望ましいだろう、という直感を働かせましょう。まずはじめに、最も左の箱に入っているものが石であるかギフトであるかを特定できるかを考えてみましょう。

質問時に使用する $A, B$ の要素数を、それぞれいったん $1$ に限定しましょう。 $A$ は必ず最も左の要素のために使うことにします。さて、 $B$ はどのように選択すれば良さそうでしょうか？実は、これについて以下のことが言えます。

ランダムに要素を選び、それを $B$ の元とする戦略を何度か取ると、高い確率で最も左の要素が石であるかどうかがわかる。

制約を見ると分かるとおり、ギフトの数は 高々 $N$ の半分以下 であるため、適当に要素を選んだ際にそれが石である確率は半分以上はあることになります。最も左の要素がギフトであることを特定するためには、 $B$ の要素として石であるものを選ぶ必要がりますが、半分以上の確率で石を選択できるため、だいたい $20$ 回程度試行しますと石を選べる確率が $1 - \left( \frac{1}{2} \right)^{20}$ くらいになるため、十分大きい確率で判定できることになります。よって、最も左の箱がギフトである場合には、 $20$ 回程度の質問で答えが得られること・そうでない場合にも「最も左の箱が石である」という情報が得られることがわかりました。

以下、最も左の箱がギフトではない (石である) 状況を考えます。今は最も左の箱、つまり $1$ 番目の箱のみについて情報が得られていますが、ここから情報を効率的に増やすにはどうすればよいでしょうか？これについては、以下のことを利用して戦略を取ると良いです。

$2^{k}$ 番目の箱について全て石が含まれている場合、「 $2^{k+1}$ 番目の箱まで全て石が含まれていること」または「 $2^{k} + 1$ 番目から $2^{k+1}$ 番目の箱の中にギフトが少なくともひとつ含まれること」のいずれかの情報が得られる

ギフトは石よりも軽いため、質問する集合に含まれている要素数が同じで、かつ一方が全て石であるような場合、もう一方が軽いと判定された時点でそこにギフトがあることがわかります。逆にそのような判定をされなかった場合は、もう一方もすべて石であることがわかります。いま、 $1$ 番目が石であるという情報をすでに持っているわけですから、この戦略が利用できるというわけです。

さて、この戦略を利用すると「添字区間 $\left[ l, r \right)$ の間に少なくともひとつギフトが存在する」ことまでは特定できます。この後にどうすればよいかと言うと、二分探索をすると良いです。というのも、 $\left[ 1, l \right)$ に関しては全て石が含まれているので、片方の集合を $\left[ 1, l \right)$ から、もう片方の集合を $\left[ l, r \right)$ から要素数が同じになるように質問すれば、先ほどと同様に「全部石の箱たち」と「一部はギフトかもしれない箱たち」との比較ができ、二分探索が可能です。

ソースコード

#ifdef LOCAL を使ってローカルでもテストできるようにしてあるので、若干冗長です、、、

enum Verdict {
    EQUAL,
    LEFT,
    RIGHT,
};

const int STONE_WEIGHT = 10;
vector<int> ref_vec;

Verdict ask_to_judge(int l1, int r1, int l2, int r2) {
    vector<int> A, B;
    for(int i=l1; i<r1; i++) A.emplace_back(i);
    for(int i=l2; i<r2; i++) B.emplace_back(i);

    printf("? %zu %zu\n", A.size(), B.size());
    for(size_t i=0; i<A.size(); i++) printf("%d%c", A[i]+1, " \n"[i + 1 == A.size()]);
    for(size_t i=0; i<B.size(); i++) printf("%d%c", B[i]+1, " \n"[i + 1 == B.size()]);
    fflush(stdout);

    int verdict;
    
#ifdef LOCAL
    int SA = 0, SB = 0;
    for(auto &a : A) SA += ref_vec[a];
    for(auto &b : B) SB += ref_vec[b];

    if(SA < SB) verdict = RIGHT;
    else if(SA > SB) verdict = LEFT;
    else verdict = EQUAL;

    vector<string> v_to_s = {"EQUAL", "LEFT", "RIGHT"};
    fprintf(stderr, "# verdict: %s\n", v_to_s[verdict].c_str());
    return (Verdict)verdict;
#endif

    string s; cin >> s;
    if(s == "FIRST") verdict = LEFT;
    if(s == "SECOND") verdict = RIGHT;
    if(s == "EQUAL") verdict = EQUAL;
    assert(s != "WASTED");
    return (Verdict)verdict;
}

void answer(int x) {
    printf("! %d\n", x+1);
    fflush(stdout);

#ifdef LOCAL
    assert(ref_vec[x] < STONE_WEIGHT);
    for(int i=0; i<x; i++) assert(ref_vec[i] == STONE_WEIGHT);
    puts("[ OK ]");
#endif
}

void solve() {
    int N, K; scanf("%d%d", &N, &K);
#ifdef LOCAL
    ref_vec.resize(N);
    printf("# Input weights.\n");
    printf("# if you want to choose stone_weight, input '-1'.\n");
    printf("# otherwise, you have to choose the weight less than STONE_WEIGHT (%d).\n", STONE_WEIGHT);
    for(int i=0; i<N; i++) {
        int v; scanf("%d", &v);
        if(v < 0) ref_vec[i] = STONE_WEIGHT;
        else {
            assert(v < STONE_WEIGHT);
            ref_vec[i] = v;
        }
    }
#endif

    Rand rnd(1333);
    for(int i=0; i<25; i++) {
        int x1 = 0, x2 = rnd.NextInt(1, N-1);
        Verdict q = ask_to_judge(x1, x1+1, x2, x2+1);
        if(q == RIGHT) {
            answer(x1);
            return;
        }
    }

    // 1st elem is stone
    int len = 1, lb = -1, ub = -1;
    for(; ; len<<=1) {
        int cnt = min(len, N - len);
        int l1 = 0, r1 = l1 + cnt;
        int l2 = len, r2 = l2 + cnt;
        Verdict q = ask_to_judge(l1, r1, l2, r2);
        if(q != EQUAL) {
            assert(q == LEFT);
            lb = l2, ub = r2;
            break;
        }
    }

    int ll = lb;
    while(ub - lb > 1) {
        int mid = (ub + lb) / 2, w = mid - ll;
        Verdict q = ask_to_judge(0, w, ll, ll+w);
        if(q == EQUAL) lb = mid;
        else ub = mid;
    }
    answer(lb);
}

int main() {
    int T; scanf("%d", &T);
    while(T--) solve();
    return 0;
}