Codeforces Round #685 Div.2-E1/E2 - Bitwise Queries 解説

数列を当てる系のインタラクティブとても好きだし得意。この前の JOI の数当てもそうだったけど、こういう問題を考えるのがとても楽しいと思えます。

問題リンク

E1 (Easy Version): https://codeforces.com/contest/1451/problem/E1
E2 (Hard Version): https://codeforces.com/contest/1451/problem/E2

問題概要

$n$ 要素からなる数列 $a$ を当てるインタラクティブ問題。解答者はプログラムの中で以下の質問をすることができます。

AND i j: $a_{i}$ と $a_{j}$ の AND を質問する。
OR i j: $a_{i}$ と $a_{j}$ の OR を質問する。
XOR i j: $a_{i}$ と $a_{j}$ の XOR を質問する。

規定の回数以内の質問で元の数列を当ててください。

制約

$4\le n\le 2^{16}$
$n$ は $2$ の冪である
Easy: 質問の回数は $n+2$ 回以内
Hard: 質問の回数は $n+1$ 回以内

考察・解法

以下数列は $0$ -indexed で表します。また、XOR を $\oplus$ 、AND を $\land$ 、OR を $\lor$ で表します。

とりあえず制約の $2$ の冪ということは忘れておいて、数列の全ての数をどうしたら求められるか考えます。
$a_{0}$ が求まっていなくてもいいので $a_{0}\oplus a_{i}$ を求めると、後で $a_{0}$ が求まった際に $(a_{0}\oplus a_{i}) \oplus a_{0} = a_{i}$ から $a_{0}$ を復元することができるので都合がいいです。ということで、全体の方針としては

$1\le i\le n-1$ を満たす全ての $i$ について、XOR 0 i を質問する。
どうにかして $a_{0}$ を求める (Easy なら 3 回以内、Hard なら 2 回以内)。

とすればいいでしょう。

問題は $a_{0}$ を求めるパートです。XOR ではどう頑張っても特定できそうには無いことが容易に分かるので、OR か AND を上手く使ってみることにします。
ここで、 $a_{0}\oplus a_{i}\ (i=0,\ 1,\ \dots ,\ n-1)$ の数列の各要素を $b_{i}$ としておくと、 $b_{i}$ は $a_{0}$ の bit だけを反転させただけであり、相対的には同じ(すなわち、 $a_{i}=a_{j} \iff b_{i}=b_{j}$ が bit 毎に成り立つということ)であることに気付きます。ここで $b$ に現れる値に重複があるかどうかで場合分けをすることができると推測します¹。

$b$ に重複した値が存在するとき
重複した値を $b_i,\ b_j$ とします。このとき $a_i,\ a_j$ は同じ値であるため、 $a_{i}\land a_{j}=a_{i}\lor a_{j}=a_{i}(=a_{j})$ です。これより、AND i j もしくは OR i j により値が具体的に求まったため、 $b_{i}\oplus a_{i}=(a_{0}\oplus a_{i})\oplus a_{i}=a_{0}$ として $a_0$ を求めることができます。よって、質問は計 $n$ 回のみで答えを得られます。
$b$ に重複した値が存在しないとき
制約より、 $a$ 及び $b$ は $[0,\ n-1$ ] の値を取ります。また、 $n$ は $2$ の冪であることより、 $a$ と $b$ の値は $0\cdots000_{(2)},\ 0\cdots001_{(2)},\ 0\cdots010_{(2)},\ \dots ,\ 1\cdots111_{(2)}$ を全て取ることが分かります。
ここで、 $b$ を適当な値にして実験をしてみます。 $a_0\land a_i=a_0\land(a_0\oplus b_i)$ を見てみることにしましょう。
例えば $n=32=2^{5},\ a_0=21=10101_{(2)}$ とし、 $b_i=7=111_{(2)}$ を満たす $i$ で上の値を求めてみます。
$a_0\land a_i\\=a_0\land (a_0\oplus b_i)\\=10101_{(2)}\land (10101_{(2)}\oplus 111_{(2)})\\=10101_{(2)}\land 10010_{(2)}=10000_{(2)}$
これを見ると、 $b_i$ のうち $1$ である bit は $a_0$ の対応する bit に関わらず $0$ 、 $0$ である bit は $a_0$ の bit が反映されることが分かります。 $b_i$ の bit が $1$ だと XOR の反転によりかならず $a_0,\ a_0\oplus b_i$ の bit が逆になるためですね。より厳密に表すと、bitwise NOT を $\lnot$ で表せば
$a_0\land a_i=a_0\land(\lnot b_i)$
であるということです。
$b_i$ は既に知っていて、 $b_0$ 以外は $1,\ 2,\ \dots ,\ n-1$ のどれかの値を取ることは分かっています。そこで、 $b_i\oplus b_j=n-1=1\cdots 111_{(2)}$ となるペア(例えば、 $1,\ n-2(=1\cdots 110_{(2)})$ )を持ってくると、
$(a_0\land a_i)\oplus (a_0\land a_j)=a_0$
となり、無事に $a_0$ が求まりました。質問は 2 回のみなので、計 $n+1$ 回で答えを得られます。

実装

$b$ をそのまま持つのと $b$ の値で逆引きするのとを併用したらいいと思います。あとは上に書いてあることを実装するだけです。
ちなみに、質問をしてその結果を返すメソッドを作ってみたらとても便利でデバッグもしやすかった(特にジャッジにあたる部分を自分で実装する際に切り分けられるのが便利)のでおすすめです。

実装を展開する

public static void Solve(Scanner cin)
{
    var n = cin.ReadInt();

    var table = new Set<int>[n];
    var axor = new int[n];
    for (int i = 0; i < n; i++)
    {
        table[i] = new Set<int>();
    }
    table[0].Add(0);
    int two = -1;
    for (int i = 1; i < n; i++)
    {
        var ret = Ask("XOR", 0, i, cin);
        if (ret == -1) return;
        table[ret].Add(i);
        axor[i] = ret;
        if (table[ret].Count > 1) two = ret;
    }
    if(two != -1)
    {
        var and = Ask("AND", table[two][0], table[two][1], cin);
        if (and == -1) return;
        var ans = new int[n];
        ans[0] = two ^ and;
        for (int i = 1; i < n; i++)
        {
            ans[i] = ans[0] ^ axor[i];
        }
        Console.WriteLine($"! {ans.Join(" ")}");
    }
    else
    {
        var one = Ask("AND", 0, table[1][0], cin);
        var notone = Ask("AND", 0, table[(n - 1) ^ 1][0], cin);
        var ans = new int[n];
        ans[0] = one ^ notone;
        for (int i = 1; i < n; i++)
        {
            ans[i] = ans[0] ^ axor[i];
        }
        Console.WriteLine($"! {ans.Join(" ")}");
    }
}

static int Ask(string q, int i, int j, Scanner cin)
{
    Console.WriteLine($"{q} {i + 1} {j + 1}");
    Console.Out.Flush();
    var ret = cin.ReadInt();
    return ret;
}

ACコード: https://codeforces.com/contest/1451/submission/99183661

感想

数当てインタラクティブしか勝たんになりました。楽しかったです。
あと、この問題のおかげで薄橙になったので嬉しいです²。
追記: CF-predictor がバグっていたようで、色変には届きませんでした。

Wow! Coder fancy_lettuce competed in Codeforces Round #685 (Div. 2) and gained +81 rating points taking place 122 https://t.co/k3xxYcrkhY

？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
なんでPredictorよりも100以上レート変動が小さいんですか？？？？ pic.twitter.com/KUjCbyjSG5
— 問題をちゃんと見る (@fairly_lettuce) 2020年11月21日

100以上じゃない、70程度か
— 問題をちゃんと見る (@fairly_lettuce) 2020年11月21日

おこです。

私は色々な $a$ を作っては $b$ がどうなるかを眺めていると、 $a$ に同じ要素があるときは $b$ で検出できるし、しかも $a_i,\ a_j$ は AND によって具体的に求められることに気付きました。しかし、制約を見ると順列になる場合は上手く行かなさそうだったので場合分けを考える、という思考になりました。↩
色変記事はアドベントカレンダーの際にまとめて書きます。↩

Growth Record of Lettuce Farm

競プロの記録・解説をします

Codeforces Round #685 Div.2-E1/E2 - Bitwise Queries 解説

問題リンク

問題概要

制約

考察・解法

実装

感想