Codeforces Round #427 Div. 2 E - The penguin's game

http://codeforces.com/contest/835/problem/E

問題概要

N要素の数列があり、そのうち2要素はYで残りの要素はXである。質問クエリとして数列のインデックスの部分集合を指定すると、それらの値のXORを知ることができる。19回以内の質問クエリで値Yを持つ2要素のインデックスを特定せよ。

2 <= N <= 1000

解法

求めたい2要素のインデックスをp1, p2とする。

場合分けして考えてみると、1回の質問クエリによって得られる情報は①「その部分集合内にYが1個ある」②「その部分集合内にYが0個or2個ある」のいずれかであることがわかる。

重要な観察として「数列のインデックスを2進数で表現したとき、n桁目のbitが立っているインデックスの集合を質問クエリで投げると、(p1 xor p2)のn桁目の値が得られる」という事実がある。なぜなら、この質問クエリの回答が①であればp1とp2は違うグループにいる=その桁の値が異なる=xorが1であり、②であればp1とp2は同じグループにいる=その桁の値が同じ=xorが0になるからである。N <= 1000より高々10回の質問クエリですべての桁のxor, すなわち(p1 xor p2)の値そのものを得ることができる。

ここで得られた(p1 xor p2)からbitが立っている桁をひとつ選び、これをx桁目と呼ぶことにする(p1 != p2より、少なくとも1桁は必ずbitが立っている)。あとはx桁目を除く各桁iに対して(x桁目のbitが立っている && i桁目のbitが立っている)という集合の質問クエリを投げると。p1かp2の片方が特定できる。(p1 xor p2)は既知なので、片方がわかればもう片方もわかる。以上でp1とp2が求まった。

前半のxorを求めるパートで高々10回、後半の特定パートで高々9回の合計19回ちょうどで制限内に質問クエリが収まる。

感想

本番結構考えてまったくわからなかったんですがnvipさんのツイートのおかげで理解できました。 ビットごとに絞り込むの自分では絶対思いつかないけど色々使えそうなんで覚えておきたい

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;


int ask(int[] q) {
    writeln("? " ~ q.length.to!string ~ " " ~ q.map!(a => a.to!string).join(" "));
    stdout.flush;
    return readln.chomp.to!int;
}

void answer(int x, int y) {
    writeln("! ", x, " ", y);
    stdout.flush;
}

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto X = s[1];
    auto Y = s[2];

    int xor = 0;
    foreach (mask; 0..10) {
        int[] q;
        foreach (i; 1..N+1) if (i & (1 << mask)) q ~= i;
        if (q.length == 0) continue;
        int ret = ask(q);
        ret = ret == X || ret == 0 ? 0 : 1;
        xor |= (ret << mask);
    }

    int b;
    foreach (mask; 0..10) if (xor & (1 << mask)) b = mask;

    int ans = 1 << b;
    foreach (mask; 0..10) {
        if (mask == b) continue;
        int[] q;
        foreach (i; 1..N+1) if ((i & (1 << mask)) && (i & (1 << b))) q ~= i;
        if (q.length == 0) continue;
        int ret = ask(q);
        ret = ret == X || ret == 0 ? 0 : 1;
        ans |= (ret << mask);
    }

    int ans2 = xor ^ ans;
    answer(min(ans, ans2), max(ans, ans2));
}