7K12 blog

猫でも分かるアルゴリズム解説

ABC170 に参加した感想

f:id:tkr987:20200615205944p:plain

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

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

 

A - Five Variables

f:id:tkr987:20200615205335p:plain

https://atcoder.jp/contests/abc170/submissions/14295713

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

 

B - Crane and Turtle

f:id:tkr987:20200615205450p:plain

https://atcoder.jp/contests/abc170/submissions/14293105

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

 

C - Forbidden List

f:id:tkr987:20200615205554p:plain

https://atcoder.jp/contests/abc170/submissions/14311131

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)になる。

http://kazune-lab.net/diary/2019/07/21/harmonic_series/

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