7K12 blog

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

ABC177 に参加した感想

f:id:tkr987:20200831143435p:plain

A1分、B7分、C9分、D8分、E56分、11WAの5完だった。

5完しても1079しかパフォーマンスが出ない。精進不足なんだよな。

 

A. Don't be late

f:id:tkr987:20200831143807p:plain

https://atcoder.jp/contests/abc177/submissions/16314199

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

 

B. Substring

f:id:tkr987:20200831143822p:plain

https://atcoder.jp/contests/abc177/submissions/16318664

rep(i, 0, Size(S)) rep(j, 0, Size(T)) if (S[i + j] != T[j]) するわけだけど、配列外参照しては困るので if (Size(S) <= i + Size(T)) continue; としたらWAして焦った。正しい条件は if (Size(S) < i + Size(T)) continue; 配列外参照はサイズと比較したとき等号必要なのが普通なので珍しい。

 

C. Sum of product of pairs

f:id:tkr987:20200831144319p:plain

https://atcoder.jp/contests/abc177/submissions/16329935

二部グラフ的な組み合わせになるかと思ったけど何も分からなかったので、方向転換して式変形と予想したら正解で分配法則だった。合計するときにSumマクロを使ったのでmod取り忘れてWAした。カス。

 

D. Friends

f:id:tkr987:20200831144444p:plain

https://atcoder.jp/contests/abc177/submissions/16336296

タイトルがfriendsなのでUnion-Findと予想できる。

 

E. Coprime

f:id:tkr987:20200831144627p:plain

https://atcoder.jp/contests/abc177/submissions/16365183

みんな大好き調和級数

順位表を見たら全人類D問題まで高速解答していて、このままだとレートが下がってしまうため気合で解いた。

 

F - I hate Shortest Path Problem

f:id:tkr987:20200831144914p:plain

一般人が実装するようなプログラミングではない。