AtCoder Beginner Contest 121

Source codesPermalink

• My submissions (AtCoder)
• My source codes (GitHub)

SolutionsPermalink

A - White CellsPermalink

$(H - h)(W - w)$ を出力する。

B - Can you solve this?Permalink

これは地道にやるだけです。

ポイントPermalink

Ruby 使って書いたからそこまで難しくはなかった。

C - Energy Drink CollectorPermalink

貪欲法。 $(A _ i, B _ i)$ を $A _ i$ の昇順に並べ換える。 $M$ 回 $B _ i$ の方を減らす。 $0$ になったら shift する( Ruby の場合)。

ポイントPermalink

$B _ i$ と $A _ i$ をごっちゃにして間違いつつあった。

D - XOR WorldPermalink

コンテスト中の解法Permalink

$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$ である。

模範解答Permalink

次の性質を使う。

任意の偶数 $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$ である。これを使うとより簡単に求まる。

ポイントPermalink

そんなに早くは書けなかった。 $0$ 桁目と $i$ 桁目の処理が違うことに気がつくのが遅かった。

OthersPermalink