AtCoder Beginner Contest 085
Updated:
10 位でした。
Source codes
Solutions
A - Already 2018
S[3] = '8' する。
B - Kagami Mochi
異なる餅の種類を数えて出力。
ポイント
set を用いた。
C - Otoshidama
10000 円札の数を $i$ とし、 5000 円札の数を $j$ とする。 1000 円札の数は $k = N - i - j$ 個だから、金額が $10000i + 5000j + 1000k = Y$ になっているかどうかをみる。全探索。 $O(N^2)$ だが $N \leq 2000$ だから十分。
ポイント
なんと $O(1)$ 解があるらしい。 rng さんの解説放送でおっしゃっていたので書いておく。
結局この問題は $x + y = N - z$ 、 $10x + 5y = Y - z$ の連立方程式の非負整数解 $(x, y, z)$ があるかどうかという問題である。 $z$ が決まれば $x, y$ は一意に定まる。そこで非負整数解がある $z$ の必要条件を求める。まず $0 \leq z \leq \min(N, Y)$ が必要である。次に、$Y - z$ が $5$ の倍数であることが必要である。すると 2 本目の式は $2x + y = (Y - z)/5$ となる。 1 本目の式と見比べると、 $N - z \leq (Y - z)/5 \leq 2(N-z)$ が必要であることがわかる。逆にこれら充たされていると、 $(x, y)$ は非負整数解として存在することがわかる。だから不等式をまず解いて、そこから $Y - z$ が $5$ の倍数になるような $z$ が存在すれば、それに決め打ちして良い。あとは連立 $1$ 次方程式を解いて $(x, y)$ を求めるだけ。ないなら -1 -1 -1 が答え。
D - Katana Thrower
$1 \leq a_i \leq b_i$ に注意する。まず刀を使って攻撃する順番と与ダメは関係ない。だから「まず刀を 1 回限り投げる。その後刀で通常攻撃をする」とルールを変更しても差し支えない。また、通常攻撃する刀は、最大ダメージを与えられる刀 1 本に絞っていい。つまり $A = \max_{0 \leq i < N} a_i$ として、通常攻撃では $A$ を与えることにする。ソートすることで $b_0 \geq b_1 \geq \dots \geq b_k \geq A \geq b_{k+1} \geq \dots$ として良い。この時 $b_0, \dots, b_k$ までは刀投げをして、あとはひたすら通常攻撃 $A$ をするのが最善である。刀投げはシミュレーション、それでもまだ HP が尽きなかったら (HP + A - 1) / A 回通常攻撃を追加するので $O(N)$ で必ず止まる。
ポイント
今回の D はアルゴリズムというより算数のような問題だったので、いつもよりスムーズに素早く解けた。
Others
10 位は嬉しいな。