A. Favorite Sound

お金を消費して聴ける回数は切り捨てで$b/a$回．聴く回数はこれと聴きたい回数$c$とのうち小さいほう． 解答例

やはり切り捨てか否かは今でもちょっと迷う．今回のような$\max k \in Z \text{ s.t. } k \le p/q$では切り捨て，$\min k \in Z \text{ s.t. } k \ge p/q$なら切り上げ，$\lt, \gt$の場合は$p/q$が整数かどうかの場合分けを加える感じだろうか．このように$k$を求める形に書き換えて考えると納得しやすいと個人的には思う．今回は$ak \le b$なので切り捨て．

B. K-th Common Divisor

約数を調べても良さそうだが，$A,B$が小さいのでループでよい．約数$d$の存在範囲は$1 \le d \le \min \{A,B\}$であるから（これが浮かばなくても$100$からループを回せばよい），この範囲の数を降順に調べ，約数かどうかを判定していけばよい． 解答例

editorialにある「$A,B$の公約数は$\gcd \{A,B\}$の約数」は言われてみれば当たり前ではあるが意外と盲点だったので覚えておきたい．

C. Unification

無くなるまで消すような解法では間に合わなそうなので別角度から．最終状態を先に考えると，異なる数字が隣り合う箇所が無くなっているはず．すなわち残った数字は一種類だけのはず．従って少ないほうの数字がすべて消費されることが分かるが，このとき操作の条件から多いほうの数字も同数だけ消費される．勿論これ以上は消せないから，よって答えは$2 \times \min \{(0$の数$),(1$の数$)\}$． 解答例

こういう系の問題は苦手だが今回は瞬間的に↑が浮かんで良かった．実装が思いっきり破壊的だがこれはStringにfoldがなく非破壊的に書こうとすると面倒なため．まあArray.initを使えばよかったのだけど．

D. Decayed Bridges

UnionFindライブラリにバグを埋め込んでいて少々困った：連結成分のサイズを返すべきところで代表元を返していた． 解答例

ある橋が無くなったときに生じる不便さは，「そのときにそれぞれの島が属する連結成分のサイズの積（連結成分が等しいときは$0$）」である（連結成分同士の直積を考えるとよい）．連結関連のあれこれはUnionFindで求めたくなるが，素のUnionFindでは橋の消滅に対応できない．実際に橋を壊すたびに連結成分の個数およびサイズは変化するから，そのままでは「橋を落としたときの連結成分のサイズ」を得るのは厳しそう．

ここで逆に最後の橋から順に橋を架けていくことを考えると，これならそのときの連結成分のサイズがそのままUnionFindで分かる．よってこの順番に積を求めていく．この値はその橋を架けることによって減る不便さ，裏を返せば橋を壊すことで発生する不便さである．求める値は$i$番目までの橋をすべて壊したときの合計であるから，先の値をまた逆順に並び替えて累積させたものが答えとなる．