AtCoder Beginner Contest 121

Updated:

AtCoder Beginner Contest 121

ソースコード

解法のメモ

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$ 桁目の処理が違うことに気がつくのが遅かった。

その他