A. Cells

残った白い部分を左上に詰めると考えやすい気がする（ABC106Aの解説のように）． 解答例

B. Can you solve this?

Yes. 数式をそのまま実装すればよい． 解答例

C. Energy Drink Collector

安いものから買っていくのがよいから，(値段,個数)のペアを値段で昇順ソートし，この順番に残り購入数が$0$になるまで買う．C++だと結構大変そうだがOCamlだと楽できる． 解答例

D. XOR World

bitごとに決めていく解法はすぐに浮かんだものの実装が複雑になってしまったため考察をした．この種の問題に適用できる定石をすっかり忘れていたので反省． 解答例

偶数とその次の数とのxorは必ず$1$である．これは最下位ビットが$0$から$1$になるだけの違いであるため．この性質を利用するために偶数と奇数のペアを基調に考えていく．

これによって$a$に最も近い偶数から$b$に最も近い奇数までのxor結果は$O(1)$で求まる：$a,b$の偶奇で場合分けすると，左端$l$は$a$が偶数のときは$a$を選べばよく，奇数のときは$a+1$．右端$r$は$b$が奇数のとき$b$，でなければ$b-1$（$l \gt r$となるような場合，すなわち$b=a,a+1$の場合は個別に処理しておく）．この中のxor結果は，偶数と隣り合う奇数のペアが$(r-l+1)/2$個存在することから，これが奇数であれば$1$，偶数であれば$0\ (\because 1 \oplus 1 = 0,\ 0 \oplus 1 = 1)$．

あとは余りを処理すればよい．まず$l=a+1$のときは$a$と先の結果とのxorが必要．右側についても同様に，$r$と$b$を比較して$r=b-1$であれば$r$とのxorも計算する．これにより所望の値が求まる．

別解1(editorial)

区間$[a,b]$に関する問題は$[0,x]$の解が求まれば$[0,b]$と$[0,a-1]$の結果から求められる場合がある，という定石を用いるのが簡単だった．いまそれぞれの範囲のxorは先の方針の一部であるから簡単に求まる．ここでxorの逆演算がxorであったことを思い出すと，$(\oplus [0,b]) \oplus (\oplus [0,a-1])$を計算すればよい（記号は適当）． 解答例

別解2(editorial)

先に述べたビットごとに決めていく解法のリベンジ．やはり$a$と$b$を同時に考えるのは厳しそう．そこでこの解法でも$[0,x]$を求める方法から考えることとする．

まずxorは桁ごとに考えることができるため，そのようにする．いま$0$から$x$までの整数を2進数表記で並べると，各ビット$i$（下から順に$0,1,...$とする）では$0$,$1$のそれぞれ$2^i$個の並びが交互に現れる．いま一つの$0...01...1$を1単位と考えると，1単位分のxorの値は$1$の個数から$i = 0$のとき$1$，それ以外のとき$0$である．$[0,x]$において，$i$ビット目までにある単位数$c$は切り捨てで$(x+1) / (2 \times 2^{i})$個であるから，繰り返し部のxor和は$i=0$のとき$c \bmod 2$，それ以外のとき$0$である．

加えてループの余り部分も考える必要がある．この長さ$l$は$(x+1)-2^{i+1} c$となる．これが$2^i$を超えている場合はその数だけ$1$が含まれるため，$(l-2^i) \bmod 2$を計算すればよい．これと先のxorの値とのxorをとれば，それがその桁の値となる． 解答例