Mister雑記

競プロやります。

Codeforces Round #563 (Div. 2) - D 「Ehab and the Expected XOR Problem」 [1900]

codeforces.com

問題

与えられた整数 N, Xに対し、以下を満たす数列 \{ a_i \}を構築せよ。

  •  1 \leq a_i \lt 2^N
  • 任意の空でない連続部分列について、そのXORは 0でも Xでもない。
  • 長さが最長である。

制約

  •  1 \leq N \leq 18
  •  1 \leq X \lt 2^{18}

考察

最長の長さ

まず解となる数列 \{ a_i \}を1つ取る。この数列は極大である、すなわち1つでも整数を先頭に加えると条件を満たさなくなる。

そこで数列 \{ a_i \}の累積XORを取り、これを \{ S_i \}とする。このとき以下が成立する:

  •  S_i \neq 0, X
  •  S_i \neq S_j \quad (i \lt j)
    • そうでない場合、 a_{i + 1} \oplus \cdots \oplus a_j = S_i \oplus S_j = 0となる。

 X \geq 2^Nの場合、部分XORが Xになることはない。一方で 1から 2^N - 1の整数で \{ S_i \}にないものがある場合、それを加えることができるので極大性に矛盾。よって l = 2^N - 1となる。


そうでない場合を考える。 T_i = S_i \oplus Xとして数列 \{ T_i \}を作る。この数列も上の条件を満たし、かつ以下も成立する:

  •  S_i \neq T_j \quad (1 \leq i, j \leq l)
    • そうでない場合、以下のようになり不適。
      •  i \lt jのとき、 a_{i + 1} \oplus \cdots \oplus a_j = S_i \oplus S_j = S_i \oplus (T_j \oplus X) = X
      •  i = j X \gt 0に矛盾。

まとめると、 \{ S_i \} \{ T_i \}をマージさせた数列はdistinctで、かつ 0 Xを含まないということになる。先と同様に極大性から、 l = 2^{N - 1} - 1となる。

構築

この流れから、Editorialでは「 \{ S_i \}を作ってからその差分を取る」という方法で構築をしていた。しかし本番の僕はそれに気づかなかったので、以下のような数列で構築をしていた。

 \displaystyle 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, \cdots

この数列は部分列のXORが 0にならない。これは同じ値を2つずつ含む部分列が存在しないことから分かる。

 X \geq 2^Nならこのままで良い。 X \lt 2^Nの場合、 Xの最下位bitが i桁目のとき、 2^iだけ飛ばして上のような数列を作るとこの部分列のXORは Xにならない( i桁目は常に 0であるため)。長さ 2^{N - 1} - 1も達成されているので、これが最適解となる。


ちなみにだが、この累積XORはグレイ・コードになっている。なぜこの構築を思いついたのか自分でも不思議だったが、過去にこの問題で自力でグレイ・コードを構築したときの記憶が残っていたのだろう。

実装例

codeforces.com

#include <iostream>
#include <numeric>
#include <vector>

// 0-indexed
template <class T, class U>
inline T kthbit(T a, U k) { return (a >> k) & 1; }


using namespace std;

vector<int> idx;
// 2^iを飛ばす処理のために必要

// 1, 2, 1, 4, 1, 2, 1, ...を出力
void rec(int N) {
    if (N < 0) return;
    rec(N - 1);
    cout << (1 << idx[N]) << " ";
    rec(N - 1);
}

int main() {
    int N, X;
    cin >> N >> X;

    if (X >= (1 << N)) {
        cout << (1 << N) - 1 << endl;

        // idxは普通に0, 1, ...で埋める
        idx.resize(N);
        iota(idx.begin(), idx.end(), 0);
        rec(N - 1);
    } else {
        cout << (1 << (N - 1)) - 1 << endl;

        // iだけ飛ばしてidxを埋める
        idx.resize(N - 1);
        bool skipped = false;
        for (int i = 0; i < N; ++i) {
            if (kthbit(X, i) && !skipped) {
                skipped = true;
            } else {
                idx[i - skipped] = i;
            }
        }
        rec(N - 2);
    }
    cout << endl;
    return 0;
}

反省

  • 累積XORに早く気づくべきだった。
    • 本番では後ろに整数を挿入することを考えていたので気づかなかった。
  • 思わぬところからグレイ・コードが出てきた。
    • 記事を書くまで気が付かなかった。