little star's memory

競プロの参加記など

AtCoder Beginner Contest 174

atcoder.jp

A~Eの5完。Eまでの動きは悪くなかったと思うけど、Fが全人類通していたので水パフォに。Fが誰も解けない難問だったらきっといいパフォだった。まぁパフォーマンスというのはそういうものだととらえて、重く考えすぎないようにするのがいいかな(外れのパチンコ台だったということで…)

A - Air Conditioner

ifと不等号を使う。ぼくは27℃で冷房を付けます。

B - Distance

$\sqrt{x ^ 2+y ^ 2}\le D$でよさそうだけど、小数は色々怖いので$x ^ 2+y ^ 2\le D ^ 2$にした。long型にするのをお忘れなく。

C - Repsept

$77...7=\frac{7}{9}(10 ^ n-1)$だ。フェルマーの小定理から、$K$が2,5と互いに素のときは、$10 ^ {K - 1}-1\equiv 0\pmod{K}$となる。なので、答えは存在する場合は$K$以下(これ本当?9の倍数のとき怪しい気がする…)。

$K$が2または5で割り切れるときは解なし。そうでないときは、$K$以下を全探索する。77...7は大きすぎるけど、$K$の倍数かどうかのみ重要なので、$K$で割った余りを考えればよい。$a_1=7, a_{n+1}=10a_n+7 \bmod{K}$という数列を考えるとよい。

ペナを恐れて必要以上に丁寧に書いた。

D - Alter Altar

swapだけでよさそう、という気持ちになるが証明できない。とりあえず投げたら通ったので正しいはず。

Rの個数をrとして、先頭r文字を取り出したときのWの個数が答え。

E - Logs

最大値の最小値といえば二分探索。これもそうだった。

答えが1になるときにバグっていて1WA。koboshi式二分探索は、すべての数が条件を満たす(or満たさない)ときに必ずバグる。

F - Range Set Query

こういうド典型問題は絶対にどこかで出題されているはずなので、ググる。すると、このサイトに出会う。これの2番目を実装するも、TLEした。Kotlinじゃなかったら通ってたのかな。

この記事のコードをコピペすると通ってたらしい。コピペで通る問題出さないでほしいなーという気持ちになったりするけど、Pond Skaterコピペで通してるのであんまりつよいこと言えない。