7K12 blog

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

ABC162に参加した感想

f:id:tkr987:20200413215228p:plain

A6分、B10分、C3分、D60分、の4完だった。

間違えてC++でなくCで提出したため、CEになってABの提出が遅れた。


A - Lucky 7

f:id:tkr987:20200413212835p:plain

https://atcoder.jp/contests/abc162/submissions/11801855

問題文に答えが書いてある。


B - FizzBuzz Sum

f:id:tkr987:20200413213135p:plain

https://atcoder.jp/contests/abc162/submissions/11816807

問題文に答えが書いてある。


C - Sum of gcd of Tuples (Easy)

f:id:tkr987:20200413213145p:plain

https://atcoder.jp/contests/abc162/submissions/11806797

問題文に答えが書いてある。


D - RGB Triplets

f:id:tkr987:20200413213154p:plain

https://atcoder.jp/contests/abc162/submissions/11848520

G1個とGより左側の全てのRとGより右側の全てのBを取り出してみる。"RRRGBBBBB"だったときにGの左と右のインデックス距離を調べるのは O(N)になる。インデックス距離が被らないなら各B毎にans+=(Rの個数)、被る場合はans+=(Rの個数-1)、これを全てのGについて同様に調べていくと O(N^2)になる。

上記処理だけだとR→G→Bしかカウントしないことになるので、RGBの順列3!パターンだけ上記処理を コ ピ ペ 笑 すると解ける 笑 無理やり処理できるコードを書くのも 実 力 なんだよな 0 (無) より 1 のほうが偉い。


E - Sum of gcd of Tuples (Hard)

f:id:tkr987:20200413213201p:plain

凡人が解くような問題ではない。


 

https://atcoder.jp/contests/abc162/submissions/11867903

なお、D問題は異なる文字3個を選ぶ組み合わせ=R*G*B通りであることとEDPC N - slimesのように中央と区間幅を全探索する考え方に気づけば可読性の良いコードが書ける。難しすぎないか。これでdif800未満とかマ?この界隈は天才しかいない。