開始少し前36.5。終了直後36.9。ここはいつから体温を書き込むスレになったんだ？Cまで瞬殺してDも解法はわりとすぐわかったので20分切れるかと思ったが細部の見落としと20分が迫る焦りが組み合わさり20:07に。いい結果ではある。
A - Favorite Sound
最初10秒くらい問題が読み込めなかった。入力が3つもあるので複雑だが、よく考えるとCで上を押さえてるだけ。B/Aのそのまま切り捨てでいい。これは1分切れるかと思いきやサンプル合わず。maxを使ってしまった。正しくはmin。「最大でもC」みたいな言葉に引きずられたんだろうね。
B - K-th Common Divisor
サンプル1でいうと、「4は、8も12も割り切る」「24を、8も12も割り切る」どちらも言えるじゃん。まあこの問題は前者だったけど。K番目に大きいで違和感はあったんだ（公倍数はいくらでも大きいものがあるから）。A*Bから下っていくコードを書こうとしていた。変だと思い読み直すと、自分は後者の解釈をしていて前者の読み方もあるというかそのほうが自然であることに気づいた。min(A, B)から下っていって、条件を満たしたらKをデクリメントしつつ、Kが0になったら出力して終わる。
C - Unification
オッ、ABCのCらしいの来たねと、紙で考察を始める。都合よく考えると少ないほうの色の数だけ取れるが。ん、それだけは必ずとれるんじゃないか。その色が残っているということは、必ずどこかでは隣り合っている。そして、それより多くは取れない。実装が単純すぎる。サンプル合ったので提出。
D - Decayed Bridges
Cまで7分で解けている。Dも早解きしたいところ。グラフっぽいが、たくさん出力するやつで、計算量をどう抑えるかという戦いか。わざとらしく「崩落」と書いてあるので逆に橋が増えていくことを考える。なんだ、ただのUnionFindじゃないか。しかし、（行き来できる）塊があちこちで成長するので具体的な出力はけっこう難しそう。まあ1段階ずつ考えれば大丈夫か。孤立したノードが集団に入るのは簡単で、その（入る前の）集団の島の数だけ「行き来できる島の組の数」が増える（どうせ同じことなので「不便さ」ではなくこちらで考えている）。じゃあ、孤立した島が二つの集団を結び付ける場合は？としばらく考えて間違いに気づく。橋を1本かける操作なので、集団と集団が合体するのを考えればいいんだ（さっきのは橋を2本かけてた）。これも島の数同士を掛け算すればいいので簡単だ。じゃあ解けた。20分切り余裕だ。あれ、サンプルでプログラムが落ちるぞ？
逆からシミュレーションするので入力は一度配列に入れることになるが、N個だけ確保していた。M個だよ！それを直しても落ちる。グラフで定番の、入力から1引くやつをやってなかった。UnionFindだから忘れても仕方ないね（は？）。さて、出力も逆向きなのに気づきそこも新たにvectorを用意し対応する。最後に、「不便さ」に変換するだけ。しかし、ここからが大変だった。答えをr[0]からr[m-1]に入れてr[0]-r[i]みたいな出力をすればいいとたかをくくっていたが、そうじゃなかった。落ち着け、サンプル出力と比較して1個ずれてる感じになっているのは何だ？そもそも、「行き来できる島の組の数」はM回変化してM+1種類あるじゃないか！M個確保した配列に全部入ってると思い込んでいた。わりと本質的な考察漏れだ。予想外の事態で、もう20分まで2分くらいしかない。結果としては、慌てて提出して20:07で全完（間に合わないのはわかっていた）。しかも、int同士の掛け算でオーバーフローの可能性があることを考えていなかったことに提出してから気づいた。5万の集団同士を最後にくっつける（最初に分断する）テストケースがあったら死んでた（45000同士ならセーフ）。N*(N-1)/2と書く（考える）のが面倒で、和で代用したのが幸運（不運）だったか？いや、N*(N-1)/2と書けばさすがに気づくか。
UnionFindで個数を扱うので、カプセル化したライブラリを使うだけでは済まない。こんな基本的な処理で手間取ったらライブラリを理解してないことになり恥ずかしいと思っていた。書き始めたらまあ書けたけど、（速度的な意味で）無駄な処理をせずしかもきれいに短時間で書くにはどうしたらいいかを考えるのは大変だった。今考えると、unite()の中で足してくのが速度的にはいいんだな。ただ、ライブラリをいじるのはすっきりしないので、個数を返す関数を作っておけばそれでいいか。そもそも、same()を呼んだらrootのすぐ下に挿げ替えるから、次にunite()を呼んだときのroot()はすぐ終わる。UnionFindの速さを信じろ。
