AとCの2完。失敗したとかじゃなくて順当にこの順位。セットとの相性という意味では運もあるけど、内容がもう順当としか言いようがない。証明ができないから競プロができない。
A - Sum equals LCM
最小公倍数は1が単位元。とりあえず大きい数を考えると、素数はその素数が必要で2個以上の和だから等しくならない。素数でないならできる？サンプルの4ができないのは2+2=2*2だからかと思ったけど、あとで8もできないことに気づいた。2と4の最小公倍数は8じゃなくて4だ。素因数が2種類あれば、最小でも2と3だし、和より積のほうが大きくなる。足りないところは1を足せばよい。素因数が1種類のとき、その数を最小公倍数にするにはその数自体が必要だ（最小公倍数は、各素因数の個数の最大値とる感じ）。Nは2以上なので素因数が0個ということもない。計算回数も試し割りで10^6.5程度なので大丈夫。
B - Sliding Window Sort 2
操作で大きくはならない。昇順になっている長さKの区間があればそこを操作すればいい。そうでないときを考える。元の順列から変わった最も左の位置が右であるほどよいので、一番右を操作するのが無難。Kより短い区間を操作することを考えると、長さは短いほうが得しそう。1 2 3 5 4 7 6 8 9 をソートするのは実質的に 5 4 7 6 だけソートしていて、これが 5 4 だけで済むとより良いといった観察をする。とすると、一番右の区間から始めて、状況が良くなるかぎり1個ずつ左にずらしていくというのがよさそう。区間の最小値より小さいものがすぐ左にあれば安全にずらせる。そうでない大きい数が現れたら、ソートすると最小値がそこへ行ってしまうのでだめ。変化する最も左の位置が左にずれたら最大じゃなくなるので。ということで実装して提出するが、なんかWAがたくさんある。
例えば K=3で5 2 4 3 1。最小値の1を外せば、「変化する最も左の位置」は変わらない。サンプルで過学習して、きっちり考えることもできず。実装の細かいミスばかり探していた。見逃してたケースがちょっと奥にあって、見えなかったね。もやがかかってたからね。
C - Social Distance on Graph
問題文に二分探索と書いてあるが信じていいかはわからない。塗るのも、塗ったうえで判定するのも大変そうだ。わからないけど、とにかく手を動かすしかない。色々様子を探っていると、二部グラフに辿り着く。XがOKかを判定するのには、重みがX未満の辺しか関係ない。同じ色同士の最小距離がX未満だったらダメ、そういうのがなければOK。X未満の辺でつながれた2頂点は違う色にする必要があり、奇閉路ができたらダメ。二部グラフがいくつかできたら、独立に考えていい。さて、距離がX未満のものは、自分と違う色の頂点1個を経由したやつだけ考えればいい。同じ色を経由したらそっちのが短いし、違う色を2個経由してもそっちのが短い。よって各頂点について最も短い2つの辺の重みの和がX未満か見ればいい。二分探索の範囲、つまり答えの最大値は、2*10^9。頂点数が3以上だから同じ色が2つは存在して、経路が辺を3個以上含んだらその中により短い同じ色のペアが存在するので最短のものは2辺以下。提出して、最後の最後で1WA。
このバグ探しも大変だったが、最後のほうのテストケース1個だけ落ちてるということは、何か極端なコーナーケースで、答えが2*10^9のケースを想定することは時間をかければできた。UpperBoundを使っていたので1を引くんだよね。つまり2*10^9まで探索して2*10^9+1で初めてダメになることを検出しないといけないから範囲は2*10^9では1足りなかった。
バグ探しに大量の時間を使った。結局、より難しい問題を考える時間は与えられなかった。頭が悪くなることで楽しみがどんどん奪われていく。この先の人生ずっとそう（たまに楽しいことはあったとしても）。
