AtCoder Beginner Contest 121

久々の数学問題で全完MaxPerf*1(1600)でした
意外にD問題のAC者が多かったみたいです

A - White Cells

問題: A - White Cells
行と列の順番は関係ないので黒く塗った行を端に寄せると、白いマスは長方形になり、２辺がそれぞれ $W-w$ 個と $H-h$ 個になるので、 $(W-w)(H-h)$ を出力すればAC。

拙解 (C++): Submission #4514229 - AtCoder Beginner Contest 121

B - Can you solve this?

問題: B - Can you solve this?
制約（ ${1\le N,M\le 20, |A_{ij}|,|B_i|,|C| \le 100}$ ）が小さく、int型でも問題文の式はオーバーフローしないことがわかるので、素直に計算して個数を数えればAC。

拙解 (C++): Submission #4516038 - AtCoder Beginner Contest 121

C - Energy Drink Collector

問題: C - Energy Drink Collector
移動コストやエナジードリンクの種類などは一切ないので、安い店から順番に（貪欲法）買えるだけ買えば最安値でエナジードリンクを買うことができる。したがって、これをシミュレートしてかかった費用の合計を出力すればAC。

拙解 (C++): Submission #4518630 - AtCoder Beginner Contest 121

D - XOR World

問題: D - XOR World
まず、排他的論理和（＝ビットごとのXOR）の基本的な事柄のうち３つについて押さえておく。
AとBの排他的論理和を $A \oplus B$ と書くことにすると、

結合則

$(A \oplus B) \oplus C = A \oplus (B \oplus C)$
が成り立つ。これは、ビットごとの演算なので1桁の場合を全列挙すれば簡単に証明できる。

逆元

$A \oplus A = 0$
が成り立つ。これも、ビットごとの演算でかつXORはビットの反転なので、同じものを入れると全てのビットが0になる。

零元

$A \oplus 0 = A$
が成り立つ。またこれも、ビットごとに考えるとすぐわかる。

以上の３つから、

$A \ge 1$ のとき

${\displaystyle\begin{eqnarray*} f(A,B)&=& 0 \oplus f(A,B) \\ &=& (f(0,A-1) \oplus f(0,A-1) ) \oplus f(A,B) \\ &=& f(0,A-1) \oplus ( f(0,A-1) \oplus f(A,B) ) \\ &=& f(0,A-1) \oplus ( 0 \oplus 1 \oplus \cdots \oplus (A-1) \oplus A \oplus (A+1) \oplus \cdots \oplus B) \\ &=& f(0,A-1) \oplus f(0,B) \end{eqnarray*}}$

$A=0$ のとき

$\displaystyle f(A,B) = f(0,B)$

というふうに、 $f(0,X)$ の形で簡単に表すことができる。こう表すと、なんらかの数学的な性質がないだろうかと期待できる。*2
そして実際に実験すると、
$\displaystyle f(0,n)=\begin{cases} n & n \equiv 0 \bmod 4 \\ 1 & n \equiv 1 \bmod 4 \\ n+1 & n \equiv 2 \bmod 4 \\ 0 & n \equiv 3 \bmod 4 \end{cases}$
とわかるので、これを実装してさきほどの式で $f(A,B)$ を求める。
制約が $0 \le A \le B \le {10}^{12}$ なので、 $A=0$ の場合を考えて場合分けをしたり、 $B\ge2^{31} > {10^9}$ の場合をを考えてlong long型で実装するなりするとAC。
証明については公式Editorialに簡潔なものがあって、これを参考にすると、
${\displaystyle\begin{eqnarray*} && 4n \oplus (4n+1) \oplus (4n+2) \oplus (4n+3) \\ &=& (4n \oplus (4n+1) ) \oplus ( (4n+2) \oplus (4n+3) ) \\ &=& 1 \oplus 1 \\ &=& 0 \end{eqnarray*}}$
となって、上の場合分けのようになるとわかる。