yukicoder No.5001 排他的論理和でランニング

問題

N個の重複のない1以上10^6以下の整数が与えられる。
ここから重複なしでM個選んですべてのXORを取ったときの値がなるべく大きくなるようにせよ。

制約

• 5 <= N <= 10^5
• 1 <= M <= N
• ただし、ジャッジには乱数で生成した値の50ケースで構成される

最終的に提出したアプローチ

最適解に1点届かない52,428,749点で10位/29人。

• 時間ぎりぎりまで以下を繰り返す
• N個から適当にM個を選び、これを初期値とする
• M個のXORを取った値の上位bitから見ていって、以下の処理をする
  • 0の場合、1にするため、そのbit以下だけ変化するようなM個側の要素1つとN-M個側の要素1つをswapする
  • 1の場合、1のままでよいが、よりスコアが上がりそうなswapができそうなら要素2個同士のswapを試す
• swapは「a xor b xor ... xor z = X」としたとき、aをa'に置き換えたときの値は「X xor a xor a'」で求められるので、O(1)で可能

最適解に1点足りないのは、上位bitから1になるように決めてく方針なので、最後のbitがうまく処理できないと11111110のような解になってしまうためだと思われる。
スコアが高い方がよいので、上位bitから1で埋められた方がよいと思ってそうした。
初期値をごちゃごちゃし続けるよりも、多点スタート的にいろんな初期値を試すのがスコアがよかった。

最適解のアプローチ

https://twitter.com/koyumeishi_/status/977210736685457408
koyumeishiさんがツイートされてたので理解のため、メモ。
アプローチは「使う要素と使わない要素のswapを時間いっぱい試す」でよいらしい。

(以下、理解が間違ってるかもなので注意)
まず、上記の問題を行列で考える。
例えば、要素がN=4個、2進数表記で(101,110,111,001)が与えられ、ここからM=2つ選ぶような場合を考える。
2進数表記の要素を横に縦向きに並べた行列をAとすると、「mod 2で計算」と「xの要素で1の数はM個、それ以外は0」という制約のもと、「Ax=b」形式で以下のように書ける。

( 1 1 1 0 )     ( 1 )
( 0 1 1 0 ) x = ( 1 )  mod 2
( 1 0 1 1 )     ( 1 )

Ax = 1  mod 2

このxを求めるのが問題。(連立1次方程式と見れる)
今回、Aの行数は、要素の最大値が10^6程度なので20bit=20行必要になる。
したがって、行列Aは、20*Nの行列。

解xが存在する場合、解の自由度はN-rank(A)。
rank(A)<=min(20, N)が成り立つので、最大でもrank(A)は20。
Nは1～10^5からランダムに選ぶので、おおよそのケースでN-rank(A)は大きい値になる。

xについて、「1の個数がM個」という制約なしで考えると、各要素は0か1なので、全部で2^N通り考えられる。
このうち、解の自由度がN-rank(A)なので、上記の式が成り立つ解xは2^{N-rank(A)}通りあると考えられる。
なので、適当にxを決めて解が見つかる確率は2^{N-rank(A)} / 2^N = 2^{-rank(A)} <= 2^{-20} ≒ 10^{-6}ぐらいになる。
したがって、10^6回探せば1回は見つかるので、比較的見つかることが期待できる。

(「解xの要素で、1の個数がM個」という制約のもとで探索する場合でも同様か、小さいケースで実験してみるとおおよそ同じ確率っぽいが、うまく式で示せない・・・orz)