7K12 blog

猫でも分かるアルゴリズム解説

東京工業大学プログラミングコンテスト2019 C - XOR Filling

f:id:tkr987:20200529213225p:plain

https://atcoder.jp/contests/ttpc2019/submissions/13679593

  • xor 演算は移項できる A xor B = X ⇔ B = X xor A
  • 「xor 演算は(ビットサイズが同じなら)X以上のB → X以下の値2個 に分解できる」と暗記する
  • つまり B = X xor B' (X < B, B' < X) が構築できる

f:id:tkr987:20200529223859p:plain
各桁の01ビットを数えても良いが、XOR演算でシンプルに解ける。A xor B = X ⇔ B = X xor A なので、-1以外の a_{i}全てとXを排他的論理和した答えをBとし、-1のうち1個をBに置換して残りを0にすれば構築できる。計算量は O(N)になる。

ただし、-1でない a_{i}がXを超えるテストケースもあるので、BがXのビットサイズを超えていたら構築不可能とする。また、BとXのビットサイズが同じ場合、X<Bでも構築可能になるので注意する。具体的には、B xor X = B'としてBをXとB'に分解する工夫をして、2個の-1をXとB'に置換する方法で構築する。