AtCoder Beginner Contest 096
Updated:
自分のためにこの記事を書いているのであるから、 ABC の問題も「自明」「やるだけ」と書くのは避けたいと思う。どんなに簡単な問題でも、次の問題を解くための礎となるはずだから、一言でも解法を書こうと思う。
Source codes
Solutions
A - Day of Takahashi
$a \leq b$ ならば $a$ 、そうでないならば $a-1$ が答え。
B - Maximum Sum
sort することで $A[0] \leq A[1] \leq A[2]$ として一般性を失わない。 $A[0] + A[1] + 2^K A[2]$ を出力する。
ポイント
200 点の問題は大体貪欲法です。
C - Grid Repainting 2
$i = 0, \dots, H-1$ に対し、 $j = 0, \dots, W-1$ に対し、 S[i][j] == '#' ならば 4 方向に # マスが 1 個でもあるかどうかを確かめる。そうでないマスが見つかったら No が答え。全部のマスで問題なかったら Yes が答え。
ポイント
よくある実装だけど ABC にふさわしい内容だと思う。
D - Five, Five Everywhere
色々解法があるが、 $55555$ 以下の素数を列挙しておき、その中から $5$ で割って $1$ 余るものを $N$ 個選び出してくれば全条件を充している。なぜなら $5$ で割って $1$ 余る数を $5$ 個足すと $5$ の倍数になるからである(しかもこれは $5$ ではない)。素数の列挙はエラトステネスの篩を使う。幸いにして $N \leq 55$ なら簡単にできてしまう。実際、以下の通りに出力された。
11 31 41 61 71 101 131 151 181 191 211 241 251 271 281 311 331 401 421 431 461 491 521 541 571 601 631 641 661 691 701 751 761 811 821 881 911 941 971 991 1021 1031 1051 1061 1091 1151 1171 1181 1201 1231 1291 1301 1321 1361 1381
ポイント
$N \leq 555$ でも解答側は上記の解法で問題ないが、 judge が大変だろうと思う。だから $N \leq 55$ になったんだろうと推測する。 judge 側は $O(N^5)$ だから。
Others
サラサラーと書いて 28 位だった。若干やさしめだったかもしれない。エラトステネスの篩は初級問題では出題が案外難しいので、いいセットだったと思う。