D - XOR World (abc121_d)

Quiz

https://atcoder.jp/contests/abc121/tasks/abc121_d

Submit

https://atcoder.jp/contests/abc121/submissions/4532962

解説ブログ

学び

  • A〜Bのとき、累積和のように0〜A, 0〜Bから求まらないか?
  • それは引き算で、XORでの引き算(打ち消しは)引きたい数をXORすること
    • a XOR a = 0
  • ビットごとに考える
    • ビットごとの1の出現回数から各ビットは求まる
    • 今回は不要
  • もっとシンプルな解法がないか?
    • 上記解法で解けるが、実装は自明ではない
    • 一方、順位表を見ると多くが通している
    • シンプルな解法がありそう
  • ペアで考える
    • 偶数 XOR (偶数+1) = 1
  • 4つ組みで考える
    • アルメリアさんのを参照
  • 実験する
    • F(0, 1)
    • F(0, 2)
    • F(0, 3)
    • ... と実験すれば周期性が見える
  • 偶数奇数のどちらで単純に解けないか?
    • どちらかが単純に解けたら+1することでもう片方(偶数・奇数)も解ける

感想

  • rated (〜1200)参加が2603人
  • Dを通したのが523人
  • 参加者もレベルも上がっている
  • 同じ時間にみんなで同じ問題を解くと一体感があって楽しいし、解説もTLで見られて理解が進む
    • Contest Driven Studying