Code Thanks Festival 2017 F Limited Xor Subset 解説

この記事は解説 Advent Calendar 2017の9日目の記事です。traP Advent Calendar 2017ではありません。(ここnariさんのパクリ)

こんにちは、xxkiritoxxです。先週はCode Thanks Festivalでしたね。略すとCTFで非常に紛らわしいです。私自身はコードフェスティバル(Thanksじゃない方)に出てたので本戦出場権は無かったんですが、暇だったので家でParallel参加していました。F問題が500点にしてはかなりの重考察を要求される問題だなあと思いながら通したのですが、完全に私の誤読が原因でした。そういう訳で想定解ではない解法が生えたので紹介させてもらおうと思います。

問題

$N$ 個の正の整数が与えられ、 $i (1 ≦ i ≦ N)$ 番目の正の整数は $a_{i}$ です。
$N$ 個の整数のうち $0$ 個以上を選んで、選んだ全ての整数のビットごとの排他的論理和を計算します。
計算結果が $K$ となるような整数の選び方の個数を $1 0^{9} + 7$ で割った余りを求めてください。
ただし、 $0$ 個選んだときのビットごとの排他的論理和は $0$ とします。

制約

入力は全て整数
$1 ≦ N ≦ 1 0^{5}$
$0 ≦ K ≦ 1 0^{5}$
$1 ≦ a_{i} (1 ≦ i ≦ N)$
$a_{1} + \dots + a_{N} ≦ 1 0^{5}$
👆こいつを誤読して
$a_{i} ≦ 1 0^{5} (1 ≦ i ≦ N)$
と勘違いしました。

解法

以下、 $a$ と $b$ の排他的論理和を $a \oplus b$ と表記します。

本問題において、集合 ${a_{1}, a_{2}, a_{3}, \dots a_{N}}$ と集合 ${a_{1}, a_{1} \oplus a_{2}, a_{3}, \dots a_{N}}$ は「本質的に同じ」です。「本質的に同じ」というのはどういうことかと言いますと、任意の $k$ に対し、この2つは「 $0$ を作れる組み合わせは何通り」「 $1$ を作れる組は何通り」・・・「 $k$ を作れる組は何通り」というのが $0 ≦ k < \infty$ の範囲で全て一致するという意味です。つまり集合の中身は変わったけど本問題においてはどんな $K$ が来ても答えは変わらないから同じようなもん・・・みたいな気持ちです。

証明をします。 $k$ を作る $a_{i}$ の選び方の個数のうち、 $a_{1}$ も $a_{2}$ も使わないで作れるパターンについては明らかに一致しますね。 $a_{2}$ を使わないで $a_{1}$ のみ使うパターンも同様に一致します。そして、 $a_{2}$ のみ使って $a_{1}$ は使わないパターンというのは、 $a_{1} \oplus a_{2}$ と $a_{1}$ の両方を使うパターンと一致します。 $a_{1}, a_{2}$ 両方を使うパターンは $a_{1} \oplus a_{2}$ を使って $a_{1}$ を使わないパターンと一致します。極めて雑ですが証明完了です。

この性質を使うことで面白い解き方が出来ます。
解法のアウトラインは、
1.ある操作を繰り返して、最初の集合と「本質的に同じ」だけどほとんど全て0で、「もし0以外の要素のみ使ってある数字を作れるならば作り方は一意」という状態を作る
2.その「ある数字」(今回は $K$ )が作れるのかを審査
3.作れないなら答えは $0$ 、作れるなら答えは $2$ の( $0$ の要素数)乗
という感じです。
口頭での説明は厳しいので、「入力例3」を解くプロセスを見せながら説明しましょう。

入力例3では $K = 3$ です。要素数が13個もあるから縦に長くて見づらいですがご了承ください。

⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ a_{1} a_{2} a_{3} a_{4} a_{5} a_{6} a_{7} a_{8} a_{9} a_{10} a_{11} a_{12} a_{13} ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞ = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 2718281828459 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞ = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 0010011100011000001010000001100000101000010001101001 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞

説明の都合で途中から2進数にしました。等号で繋がってるのおかしいですね。ごめんなさい。
さて、こいつを「本質的に同じ」な別の集合に作り変えましょう。まず $a_{1}$ から順に調べていって、先頭ビットが立っているものを探します。今回は $a_{4}$ が見つかりました。
そこで、 $a_{4}$ 以外で先頭ビットが立っているものは全て $a_{4}$ とのXORを取りましょう。既に示した性質より、この操作によって生まれる集合は最初の集合と「本質的に同じ」になります。

⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 00100111000110000010 1000 \oplus 1000 0001 1000 \oplus 1000 0010 1000 \oplus 1000 010001101001 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞ = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 0010011100011000001000000001000000100000010001100001 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞

次も同じようなことをします。まず $a_{1}$ から順に前から2番目のビットが立っているものを探します。 $a_{2}$ が見つかりました。以降、2番目のビットが立っているものは全て $a_{2}$ とのXORを取ります。
この処理をする上での注意なんですが、「前から2ビット目が立ってるもの」なら何を取ってきてもいいわけじゃないです。「前から2ビット目が立っていて、なおかつ先頭ビットが立っていないもの」を取ってきてください。
そうすると、集合はこのように変化します。

⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 0010011100011000001000000001000000100000 0100 \oplus 0111 0110 \oplus 0111 0001 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞ = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 0010011100011000001000000001000000100000001100010001 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞

前から3ビット目も同様に操作します。「前から3ビット目が立っているもので前から2ビット目以降が立っていないもの」には最初に $a_{1}$ がヒットします。
ただし、実装の際に面倒なので、前から3ビット目は立っているけど2ビット目も立っている $a_{2}$ は $a_{1}$ とのXORを取らないことにします。

⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 0010011100011000 0010 \oplus 0010 000000010000 0010 \oplus 0010 0000 0011 \oplus 0010 00010001 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞ = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 0010011100011000000000000001000000000000000100010001 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞

いい感じに0の要素が増えてきました。この集合でも最初の集合と「本質的に同じ」という性質は残っています。最後に最終ビットについても操作しちゃいましょう。条件を満たすもので最初にヒットするのは $a_{4}$ です。

⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 001001110001100000000000 0001 \oplus 0001 000000000000 0001 \oplus 0001 0001 \oplus 0001 0001 \oplus 0001 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞ = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 0010011100011000000000000000000000000000000000000000 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞

さて、こうした操作によって9つの0と4つの非零の値が出来ました。この集合は最初の集合と「本質的に同じ」です。目的の数 $K$ を作るにあたり、0のものは使っても使わなくてもどっちでもいいのは明らかですが、非零の要素については必ず使うか必ず使わないかの2択になります。厳密に示したければ帰納法を使えばいいのでしょうが、雑に理由を説明すると「 $a_{i}$ より2進数での桁数が大きいものについて使うか使わないかが全て決まっているとき、 $a_{i}$ と同じ桁の値は $a_{i}$ を使うか使わないかのみに依存するから」という感じです。

今までの考察により、本問の答えは「最後に残った非零の要素を使って $K$ を作れなければ答えは $0$ 、作れたら答えは $2^{9}$ 」です。これを確かめるには先頭ビットから順に使うか使わないか決めていって、最終的に作ることが出来るかを検証するだけです。この手順は操作を全て終えた後に行おうとすると意外と大変なので、上の操作を行いながら平行して検証出来るように実装するとよいでしょう。実装例は下に私のコードを貼っておきますので、そちらを参照してください。

さて、計算量を概算しましょう。一回の操作に $O (N)$ かかり、操作の回数は $K$ もしくは $max a_{i}$ の2進数での桁数ぐらいです。しかし、この操作は $lo g K$ 回やってもうまくいきません。例えば $K = 1, a_{1} = 8, a_{2} = 9$ のときはどうでしょう。一番後ろのビットだけに注目するとうまく $a_{1}$ を処理出来ません。失敗です。いっぽう $lo g max a_{i}$ やれば確実にうまくいきます。
よって、この解法の全体での計算量は $O (N lo g max a_{i})$ となります。かなり高速になりますし、最初の条件を誤読したままでもこの計算量なら通ることが分かります。

実際の提出

https://beta.atcoder.jp/contests/code-thanks-festival-2017-open/submissions/1822899
これはコンテスト中に書いたものです。焦っていたので途中で不要なソートをしていて、そのため $O (N lo g N lo g max a_{i})$ というかなり変なオーダーになっています。ソートはソートでもqsortなのが味わい深いですね。
https://beta.atcoder.jp/contests/code-thanks-festival-2017-open/submissions/1834702
数日後に書き直しました。かなり高速になっています。
https://beta.atcoder.jp/contests/code-thanks-festival-2017-open/submissions/1835196
時間計算量が落とせそうになかったんで空間計算量を落としてみたところ実行時間も若干改善しました。2017/12/08現在では実行時間、使用メモリ共に最小のようです。計算の順序を†ちょっと†工夫することで空間計算量は $O (lo g max a_{i})$ にまで落ちます。

まとめ

制約はちゃんと使おう！

余談

ところで、この操作完全にガウスの消去法なんですよ。線形代数の知見が生きたので面白い問題だなあと思うと同時に（これ本当に500点か・・・？）と思っていたのですが、解説読んだら遥かに簡単な解法があってブチ切れてしまいました。

Code Thanks Festival 2017 F Limited Xor Subset 解説

問題

制約

解法

実際の提出

まとめ

余談

この記事をシェア

関連する記事