LinuxとMacと俺と

　ARC092/ABC091 D - Two Sequencesを解いていきます。 問題 https://beta.atcoder.jp/contests/arc092/tasks/arc092_b 感想 　本番でC問題も解けず、焦ってこの問題見たら絶望しました。 　何か規則性はないものかと必死で探して見たものの見つからず、解ける気がしませんでした。今後のために解法を書いておく事にしました。 　結果はもちろん0完。。。 解法 　aとbを足した全ての値を全て計算すると、計算量はO(n^2)となり最大で400億になってしまうので間に合わない。 　そこで二進数の各位ごとに計算する。 　　 10進数 2進数 0 0 1 1 2 10 3 11 4 100 5 101 6 110 7 111 8 1000 9 1001 10 1010 11 1011 12 1100 13 1101 14 1110 15 1111 16 10000 　 　この表を見ると2^kの位は０と１が2^k個づつ交互に並んでいることがわかる。 　よって、 　ai + bj の ２^kの位 の値は、ai + bj の値が... 　0 ≤ ai+bj < 2^k の時 0    2^k ≤ ai+bj < 2*2^k の時 1    2*2^k ≤ ai+bj < 3*2^k の時 0    3*2^k ≤ ai+bj < 4*2^k の時 1 　4*2^k ≤ ai+bj < 5*2^k の時 0    5*2^k ≤ ai+bj < 6*2^k の時 1   ...... となる。 　これは、mod(2*2^k)としてしまっても構わないので、 　　　　ai ≡ n (mod 2*2^k) 　　　　bj ≡ m (mod 2*2^k) 　とすると、 0 ≤ n+m < 2^k の時 0 2^k ≤ n+m < 2*2^k の時 1 2*2^k ≤ n+m < 3*2^k の時 0 3*2^k ≤ n+m < 4*2^k の時 1  　n+m < 4*2^k より、場合分けはこれだ