CODE THANKS FESTIVAL 2017-F Limited Xor Subset
概要
最大10万長の数列が与えられる。この数列は和が10^5以下を満たす。
この数列の部分列のうち、XORしたらKになるのはなん通り存在するのか？
ACするまで
1. 明らかにデカデカと書かれてる制約がキーであるとわかる。
2. 部分列の数え上げの僕の知る限りの一番効率がいいのは動的計画法。動的計画法で数え上げをしてみる。
3. 数え上げ方が悪い、バグる。
4. 計算量を解析してみると実は上から抑えられるタイプである。よって、もっとも単純な動的計画法でも通る。
5. 書く->AC!
考察
部分列の数え上げは、数え上げ対象が特殊なタイプ以外は動的計画法で丁寧に数え上げるしかない。しかし、この問題の一見の計算量は、となる、TLEする。
しかし、実際の計算量を詳しく解析してみる。
和が10^5までしかないことを利用すると、種類数最多は1, 2, 3, 4...と続けても500通りは超えないとわかる。(500 * 501 / 2 =125250 )このことから、もともと用意していた
dp[i][j] := i個目の数字を使うかどうかまで見て、xorがjになる部分列の場合の数
と定義されていたDPの二つ目の添え字を考えてみる。
XORしても、AとBの立ってる最上位bitより上でbitが立つ二進数が答えとはなりえない。(例でいうと、3 xor 5 = 6となり、最上位bitは4の位となり、8の位以上のbitが立つものが答えになることはない)このことから、部分列のXORが作れる値は、一番多い場合でも、上記の1, 2, 3, 4...では最大2^8=256の位が立つものまでしかないので、たかだか多くても2^9-1=511通り程度しかない。
つまり、よく考察すると、作れる数字はたかだか500個程度しかないとわかる。
このような上限は大きめだけど、中身はスカスカの場合は、連想配列(C++でいうとstd::map)を利用してDPを組むことでうまくいく場合がある。空間計算量は単純にO(K)からO(要素数個)になり、時間計算量はmapだと平行二分木なので、O(K)から要素数個をXとすると、O(X log X)になる。今回の場合は、このアプローチをすると時間計算量も空間計算量も改善できる。
詳しい実装はソースコードを参照。ほぼ動的計画法と同じである。
ACソースコード：
Submission #8442604 - CODE THANKS FESTIVAL 2017(Parallel)
一言
こういうのを素早く正確に気付き通す力って大事だよね。
