ABC170 に参加した感想

f:id:tkr987:20200615205944p:plain

A1分、B4分、C13分、の3完だった。

今回のような簡単なセットを落とすようだと一生緑のまま。ゴミ。

A - Five Variables

f:id:tkr987:20200615205335p:plain

頑張ってタイピングする。

B - Crane and Turtle

f:id:tkr987:20200615205450p:plain

式変形すると $O(1)$ で分かる？かもしれないけど、面倒なので $O(N^2)$ で十分。

C - Forbidden List

f:id:tkr987:20200615205554p:plain

pが100個しかないのだからpが如何なる整数だろうとX±100に答えがある。Xに近い数字から順番に数列に存在するかどうか調べるだけで良い。調べるときに二分探索を使うと $O(N \log N)$ になる。なお、制約上二分探索を使わなくてもTLEしないので自由に実装は出来る。

D - Not Divisible

f:id:tkr987:20200615205723p:plain

調和級数の解析により逆数の総和は $O(\log N)$

数列に同じ整数が多数含まれると $O(N^2)$ になってしまうが、2回目以降の同じ整数はcontinueすることで調和級数を満たし、全体計算量は $O(N \log N)$ になる。

知識として知っていたのに気づけなかった。ゴミ。頭悪すぎて萎えた。

7K12 blog