Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 173

4完。29:56。

別に悪いわけではないし、レートも上がるけど、今日は負けた気しかしない・・・。

各問題

A - Payment

1000 - N % 1000とやってしまうと、Nが1000の倍数の時1000になってしまうのでそれを注意します。(1000 - N % 1000) % 1000とやるのが定石で、覚えておいて損はありません。(自分はすぐ忘れてif文書いちゃうんですけど)

B - Judge Status Summary

数えて、出力するだけです。なんだこれ?

C - H and V

制約が極端に小さいので、いかにも全探索してほしそうにしています。

というわけで、縦と横でbit全探索をすると通ります。

まあまあ実装が面倒そうなので、飛ばしてDを先にやったのは内緒です。(そして実際に添え字地獄にはまって割と苦労しました)

D - Chat in a Circle

実験すると、Aを降順にソートしてA_1 + A_2 \times 2 + A_3 \times 2 + A_4 \times 2 + ...が最適っぽいとわかります。(証明はしてません・・・)

E - Multiplication 4

0が最適な時、正の数にできる時、負の数にならざるを得ない時などがあり、鬼のような場合分けをして頑張りましたが、WA x 6 -> WA x 5 -> WA x 3 となり、まだ残っているWAが何故出るかは理解できたのですが(負数を奇数回掛けてしまうことがあったっぽい)、それを直すには至らず時間切れとなりました。いやー、これは悔しいなー。

F - Intervals on Tree

一応問題文は読みましたが、読んだだけ。

まとめ

Eが、難しい考察は不要で実装頑張ればなんとかなった問題だと思うので、それを通せなかったのは自分としては痛いですね。

まあHighestが見えるところまで回復してきたのでとりあえずよしということで。

f:id:mdstoy:20200705225835p:plain