7K12 blog

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

ABC172 に参加した感想

f:id:tkr987:20200628201907p:plain

A問題1分、B問題1分、C問題23分、の3完だった。

また調和級数に負けた。しかし、今回は完全に数学力不足で考察しても気づかない類の問題だったので、どうしようもなかった。国立二次の問題集を買って整数問題の例題を全て解いておいたのだが、その程度だとD問題の数学に歯がたたないので困っている…1年前も3完できていたので上達が見られない。一生水色には到達できない。

 

A - Calc

f:id:tkr987:20200628200734p:plain

https://atcoder.jp/contests/abc172/submissions/14727291

頑張ってタイピングする

 

B - Minor Change

f:id:tkr987:20200628200849p:plain

https://atcoder.jp/contests/abc172/submissions/14724754

う 笑

 

C - Tsundoku

f:id:tkr987:20200628201104p:plain

https://atcoder.jp/contests/abc172/submissions/14747895

累積和を作って2重ループのうち片方を二分探索して1重ループにすればok

累積和はNyaGadget::DS_NyaaCumulativeSumでライブラリ化してるので貼るだけ

 

D - Sum of Divisors

f:id:tkr987:20200628201550p:plain

分からなかった。普通に処理すると O(N \sqrt N)でTLEするので、メモ化するかDP的な処理をするかと思った。調和級数も一応考察していたが、どの部分が調和級数になるのか分からなかった。