AtCoder Beginner Contest 121
Updated:
Source codes
Solutions
A - White Cells
$(H - h)(W - w)$ を出力する。
B - Can you solve this?
これは地道にやるだけです。
ポイント
Ruby 使って書いたからそこまで難しくはなかった。
C - Energy Drink Collector
貪欲法。 $(A _ i, B _ i)$ を $A _ i$ の昇順に並べ換える。 $M$ 回 $B _ i$ の方を減らす。 $0$ になったら shift する( Ruby の場合)。
ポイント
$B _ i$ と $A _ i$ をごっちゃにして間違いつつあった。
D - XOR World
コンテスト中の解法
$F(x) = 0, 1, \dots, x$ を xor した値、ただし $F(-1) = 0$ とする。
とすると、答えは $f(A, B) = F(B) \mathop{xor} F(A - 1)$ である。以下 $F(x)$ を求める。
2 進数表記で考える。 $L = x + 1$ とする。
- $0$ 桁目について： $L \% 4 = 2, 3$ の時は $1$ でありそれ以外は $0$ である。
- $i$ 桁目 ($1 \leq i \leq 60$) について： $L$ を $2^{i + 1}$ で割った余りを $C$ とする。 $C < 2^i$ ならば $0$ である。 $C \geq 2^i$ ならば、 $C - 2^i$ が奇数なら $1$ であり、それ以外は $0$ である。
模範解答
次の性質を使う。
任意の偶数 $n \in \mathbb{N}$ に対し $n \mathop{xor} (x + 1) = 1$ 。
すると
\[
\begin{align}
F(x) &= (0 \mathop{xor} 1) \mathop{xor} (3 \mathop{xor} 4)
\mathop{xor} \dots \mathop{xor} x \\
&=
\begin{cases}
1 \mathop{xor} 1 \mathop{xor} \dots \mathop{xor} 1 \mathop{xor} x & (x \% 2 = 0), \\
1 \mathop{xor} 1 \mathop{xor} \dots \mathop{xor} 1 & (x \% 2 = 1).
\end{cases}
\end{align}
\]
となる。最初の $1 \mathop{xor} \dots \mathop{xor} 1 = ((x + 1) / 2) \% 2$ である。これを使うとより簡単に求まる。
ポイント
そんなに早くは書けなかった。 $0$ 桁目と $i$ 桁目の処理が違うことに気がつくのが遅かった。