2017年12月9日 | ブログ記事

Code Thanks Festival 2017 F Limited Xor Subset 解説

xxkiritoxx

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

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

問題

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

制約

入力は全て整数
1N1051\leqq N\leqq 10^5
0K1050\leqq K\leqq10^5
1ai(1iN)1\leqq a_i(1\leqq i\leqq N)
a1++aN105a_1+\ldots +a_N\leqq10^5
👆こいつを誤読して
ai105(1iN)a_i\leqq10^5(1\leqq i\leqq N)
と勘違いしました。

解法

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

本問題において、集合{a1,a2,a3,aN}\{a_1,a_2,a_3,\ldots a_N\}と集合{a1,a1a2,a3,aN}\{a_1,a_1 \oplus a_2,a_3,\ldots a_N\}は「本質的に同じ」です。「本質的に同じ」というのはどういうことかと言いますと、任意のkkに対し、この2つは「00を作れる組み合わせは何通り」「11を作れる組は何通り」・・・「kkを作れる組は何通り」というのが0k<0\leqq k < \inftyの範囲で全て一致するという意味です。つまり集合の中身は変わったけど本問題においてはどんなKKが来ても答えは変わらないから同じようなもん・・・みたいな気持ちです。

証明をします。kkを作るaia_iの選び方の個数のうち、a1a_1a2a_2も使わないで作れるパターンについては明らかに一致しますね。a2a_2を使わないでa1a_1のみ使うパターンも同様に一致します。そして、a2a_2のみ使ってa1a_1は使わないパターンというのは、a1a2a_1\oplus a_2a1a_1の両方を使うパターンと一致します。a1,a2a_1,a_2両方を使うパターンはa1a2a_1\oplus a_2を使ってa1a_1を使わないパターンと一致します。極めて雑ですが証明完了です。

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

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

(a1a2a3a4a5a6a7a8a9a10a11a12a13)=(2718281828459)=(0010011100011000001010000001100000101000010001101001)\begin{array}{c} \left( \begin{array}{c} 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} \end{array} \right) = \left( \begin{array}{c} 2 \\ 7 \\ 1 \\ 8 \\ 2 \\ 8 \\ 1 \\ 8 \\ 2 \\ 8 \\ 4 \\ 5 \\ 9 \end{array} \right) = \left( \begin{array}{c} 0010 \\ 0111 \\ 0001 \\ 1000 \\ 0010 \\ 1000 \\ 0001 \\ 1000 \\ 0010 \\ 1000 \\ 0100 \\ 0110 \\ 1001 \end{array} \right) \end{array}

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

(0010011100011000001010001000000110001000001010001000010001101001)=(0010011100011000001000000001000000100000010001100001)\begin{array}{c} \left( \begin{array}{c} 0010 \\ 0111 \\ 0001 \\ 1000 \\ 0010 \\ 1000 \oplus 1000 \\ 0001 \\ 1000 \oplus 1000 \\ 0010 \\ 1000 \oplus 1000 \\ 0100 \\ 0110 \\ 1001 \end{array} \right) = \left( \begin{array}{c} 0010 \\ 0111 \\ 0001 \\ 1000 \\ 0010 \\ 0000 \\ 0001 \\ 0000 \\ 0010 \\ 0000 \\ 0100 \\ 0110 \\ 0001 \end{array} \right) \end{array}

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

(001001110001100000100000000100000010000001000111011001110001)=(0010011100011000001000000001000000100000001100010001)\begin{array}{c} \left( \begin{array}{c} 0010 \\ 0111 \\ 0001 \\ 1000 \\ 0010 \\ 0000 \\ 0001 \\ 0000 \\ 0010 \\ 0000 \\ 0100 \oplus 0111 \\ 0110 \oplus 0111 \\ 0001 \end{array} \right) = \left( \begin{array}{c} 0010 \\ 0111 \\ 0001 \\ 1000 \\ 0010 \\ 0000 \\ 0001 \\ 0000 \\ 0010 \\ 0000 \\ 0011 \\ 0001 \\ 0001 \end{array} \right) \end{array}

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

(0010011100011000001000100000000100000010001000000011001000010001)=(0010011100011000000000000001000000000000000100010001)\begin{array}{c} \left( \begin{array}{c} 0010 \\ 0111 \\ 0001 \\ 1000 \\ 0010 \oplus 0010 \\ 0000 \\ 0001 \\ 0000 \\ 0010 \oplus 0010 \\ 0000 \\ 0011 \oplus 0010 \\ 0001 \\ 0001 \end{array} \right) = \left( \begin{array}{c} 0010 \\ 0111 \\ 0001 \\ 1000 \\ 0000 \\ 0000 \\ 0001 \\ 0000 \\ 0000 \\ 0000 \\ 0001 \\ 0001 \\ 0001 \end{array} \right) \end{array}

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

(00100111000110000000000000010001000000000000000100010001000100010001)=(0010011100011000000000000000000000000000000000000000)\begin{array}{c} \left( \begin{array}{c} 0010 \\ 0111 \\ 0001 \\ 1000 \\ 0000 \\ 0000 \\ 0001 \oplus 0001 \\ 0000 \\ 0000 \\ 0000 \\ 0001 \oplus 0001 \\ 0001 \oplus 0001 \\ 0001 \oplus 0001 \end{array} \right) = \left( \begin{array}{c} 0010 \\ 0111 \\ 0001 \\ 1000 \\ 0000 \\ 0000 \\ 0000 \\ 0000 \\ 0000 \\ 0000 \\ 0000 \\ 0000 \\ 0000 \end{array} \right) \end{array}

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

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

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

実際の提出

https://beta.atcoder.jp/contests/code-thanks-festival-2017-open/submissions/1822899
これはコンテスト中に書いたものです。焦っていたので途中で不要なソートをしていて、そのためO(NlogNlogmaxai)O(N \log N \log \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(logmaxai)O(\log \max a_i)にまで落ちます。

まとめ

制約はちゃんと使おう!

余談

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

この記事を書いた人
xxkiritoxx

SAOを見たことはありません

この記事をシェア

このエントリーをはてなブックマークに追加

関連する記事

2018年3月18日
SamurAI Coding 2017-18に参加しました
ninja
2018年3月6日
ICPC World Finals 2018にninjaribatonが出場します!
nari
2017年12月20日
ICPCアジア地区つくば大会参加記
baton
2017年12月14日
yukicoder Advent Calendar Contest 2017 11日目 Day of the Mountain 解説
nari
2017年12月6日
JAG模擬地区予選2017 D Revenge of the Broken Door 解説
nari
2017年11月26日
CODE FESTIVAL 2017 参加記
xxkiritoxx

活動の紹介

カテゴリ

タグ