AtCoder Beginner Contest 105
Updated:
Source codes
Solutions
A - AtCoder Crackers
小学 1 年生のように 1 つずつ配っていくことを想像する。 $N$ が $K$ で割り切れれば $0$ 、そうでなければ $1$ である。
ポイント
解説 PDF によると N%K != 0 を int 型に変換すれば出力になる。これは思いつかなかったし、頭がいいと思う。しかし、こういう小技は、だいたい私がうっかり間違う原因になるので、参考程度に捉えておく。
B - Cakes and Donuts
コンテスト中に思いついた解法
算数で求めることも可能だが、動的計画法を使う。
$DP[i] = i$ ドルの買い方があれば
true、そうでなければfalse
と定める。
- 初期状態： $DP[0] = $
true、それ以外false。 - 答え： $DP[N]$ 。
- 遷移： $i = 0, \dots, 100$ に対し $DP[i] = $
trueならば $DP[i + 4] = DP[i + 7] = $trueと定める。配列は大きめにとっておくか、または Ruby で書く。
解説 PDF の模範解答(改)
2 重ループで求める。 $i = 0, \dots, 100$ に対し、 $j = 0, \dots, 100$ に対し、 $4 i + 7 j$ が $N$ となるかどうかを確かめる。
C - Base -2 Number
着想
普通の $2$ 進数を考える。 $2$ 進数の場合、下の桁から決定できる。 $k = 0, 1, \dots, 40$ に対し、 $N$ を増減させる。 $N$ が $2^{k+1}$ で割り切れないならば、 $2^k$ の桁は 立たせるしかない 。後ろの方でどう頑張っても、それらは $2^{k+1}$ で割り切れるのだから。そして、 $N -= 2^{k}$ とする。これを繰り返す。
解答
$(-2)$ 進数の場合も、ほぼ同様である。下の方から見ていき、立たせるしかない桁は立たせるしかない。 $N \gets N - (-2)^{k}$ とするところだけ違う。それ以外は同じ。あとは出力する際に leading zeros は出力しないことに注意。ただし $0$ だけは $0$ と出力する。
実装上のポイント
解説放送を見てもっと簡単に実装できることに気がついた。 \[ N = S_0 (-2)^0 + S_1 (-2)^1 + S_2 (-2)^2 + \dots + S_k (-2)^k \] であるが、 $N = S_0 \in \mathbb{Z}/2\mathbb{Z}$ であるから、まず $S_0$ が確定する。次に、式変形をすると、 \[ \frac{N - S_0}{-2} = S_1 (-2)^0 + S_2 (-2)^1 + \dots + S_k (-2)^{k-1} \] であるから、左辺を $N$ で置き換え、同じことをすると $S_1$ が確定する。こうして左辺が $0$ になるまで続ける。順次確定する。
ポイント
これは最初解法が全然思いつかなかった。 D から先にやってよかった。 必要条件を列挙していたら、実は十分条件 のパターンである。今回は十分性は、親切にも、問題文に注釈されている。
D - Candy Distribution
$0$-indexed とする。 $B_{-1} = 0$, $B_k = \sum_{i = 0}^k A_k$ と定める。 $A_l + A_{l + 1} + \dots + A_r = B_r - B_{l - 1}$ であるから、これが $M$ の倍数であるということは、 $B_r = B_{l - 1} \in \mathbb{Z}/M\mathbb{Z}$ と同値である。ゆえに、 $-1 \leq x < y < N$ であって $B_x = B_y \in \mathbb{Z}/M\mathbb{Z}$ なる組 $(x, y)$ を数えるとそれが答えとなる。 $y = 0, \dots, N - 1$ に対し、
\[
X[i] = \sharp \{ -1 \leq x < y \mid B_x = i \in \mathbb{Z}/M\mathbb{Z} \}
\]
と定め、 $y$ ごとに更新し、 ans += X[sum]; とする。 $M \leq 10^9$ は十分大きいので、 map<ll, ll> X; で記憶するのが賢明な判断だ(ホームズ風に)。
Others
A - sample: 3, tle: 2.000, time: 01:12, from_submit: 14:36
B - sample: 3, tle: 2.000, time: 01:40, from_submit: 12:56
C - sample: 3, tle: 2.000, time: 07:21, from_submit: 00:00
D - sample: 3, tle: 2.000, time: 05:36, from_submit: 07:20