AtCoder Beginner Contest 105

Updated:

AtCoder Beginner Contest 105

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