ABC120 参加メモ

https://atcoder.jp/contests/abc120 35分で全完できました！ 3237人中203位でした。

rating

980->1121(+141). 次回は水色いけるかな？

A

min(C, A // B) を出力するだけです。

B

A, B<=100なので内包表記でゴリ押しできます。 [i for i in range(1, 100 + 1) if A % i == 0 and B % i == 0][-K] が解です。 大きい方からK番目であることに注意しましょう。 Pythonのリストに対して[-i]にアクセスすると後ろからi番目の要素を得ることができます。

C

貪欲で通らないケースが思いつかず、未証明で貪欲コードを提出しました。 どうやら、 2min(S.count('0'), S.count('1')) で通るようです。エレガント。

D

1番目から順に橋が失われたとき、それぞれの不便さを求めるのはとても難しいのでは？と思いました。 しかし逆にM番目から順に橋が作成されると考えると考えやすそう。 そこで、M番目から順に解を求める方針にします。

最初の不便度はN*(N-1)/2です。 ここから、橋が増えるにつれて、不便度がどう減るかを計算します。 Union-FInd木を使って、結合する島が異なるグループかどうかを判定。 異なるグループならば、結合するグループの要素数の積だけ不便度が減ります。 例えば、3個のグループと4個のグループを結合する場合、不便度は12減ります。 これを1番目の橋まで順に計算するだけです。