AtCoder Beginner Contest 121：D - XOR World
問題
解法
A, B >= 10^12 と大きいので愚直な計算では TLE となってしまう．
ここで，答えとなる数の k bit 目を明らかにすることを考える．0 から順番に数を 2 進数表記で書いて眺めてみると，1 bit 目は 0, 1, 0, 1, ... と 0, 1 の塊が永遠と並んでいる．同様に k bit 目は
0, 0, ... , 0, 1, 1, ... , 1（0, 1 はそれぞれ 2^(k-1) 個）
となっていることに気づく．これを踏まえて，0 ~ B の k bit 目に立っている bit の数と 0 ~ A の k bit 目に立っている bit の数を数え，前者から後者を引いた数が奇数であれば答えの k bit 目は 1 であり，そうでなければ 0 である．O(logB)．
解答
ちょっと焦ってしまったが No WA で通せたのでよかった．
AtCoder Beginner Contest 121：C - Energy Drink Collector
AtCoder Beginner Contest 118：D - Match Matching
問題
解法
dp(i) := マッチ棒を i 本ちょうど使って出来る最大の数
と DP を定義する．このとき，遷移時に A_i を全て試し，その中で最大の数を DP の答えにすればよい．答えとなる数は非常に大きくなるので，文字列として扱う．O(NM)．
解答
