D - XOR World (abc121_d)

解説ブログ

学び

  • 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

久しぶりに解き直したら洗練した

// 0～aまでのXOR
ll f(ll a){
  if(a<0)return 0;
  if(a%4==3)return 0;
  if(a%4==0)return a;
  if(a%4==1)return a^(a-1);
  if(a%4==2)return a^(a-1)^(a-2);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll a,b;cin>>a>>b;

    ll ans = f(b)^f(a-1);
    p(ans);
    
    return 0;
}