5完。結果は順当というところ。とにかく多くの問題をコンテスト中に考えたいので、30分残してF以外を通せたのは良い。
A - Cabbages
普通に場合分けしたけど1分45秒かかった。この実装はかなり重い。
B - Bouzu Mekuri
かなり怖い見た目をしているが、シミュレーションするだけで簡単。
C - Colorful Candies
難しい見た目。区間をずらしながらstd::mapで種類数の変化を監視。実装もけっこう大変。重いCだった。
D - National Railway
10^6個から2つ選ぶのは広い。1つめの駅の場所や2駅の距離を固定して考えてみるが間に合いそうにない。先にEをやった。
具体的な経路を考えていると、DPを思いついた。なんかデータ構造で答えが出る問題に見えちゃってたな。2駅が左上と右下の関係にあると仮定すれば、右か下にだけ動いて到達すればどんな経路でもいい。DPで、1つめの駅のコストとそこまでの移動コストの和の最小を計算していく（左上隅も含め全マスをINFで初期化し配るDP）（各マスでそれと2つめの駅のコストを足して最小値を更新していく）。左下と右上のケースもあるので、Aを上下反転してもう1回やる。わかってしまうと全然難しくはないんだよなあ。
E - Ring MST
少し考えると最小全域木だとわかる（気づかなかったけど問題名にMSTとあった）。つまりコストの低い辺から貪欲に使っていけばいい（コストが同じものが複数種類あった場合でもどんな順番でもいいのすごいよね）。まずコスト最小のA_iとNのgcdが1ならそこで終わり。そうでないとき、リングはA_i個で他の割り切れないやつ使えば全部つなげると思っちゃってWA。何も考えてない。ペナルティを避けるよりも、他の問題を考える時間を残したいと思っていた。リングはgcd(A_i, N)個だと気づいて提出してもWAで、まあ2WAになると"気づかされる"よね。今度は考慮に沈む。1回で全部つながるわけなくてgcd個まで減るだけだ。gcdが減ったぶんだけそこでコストを払う。ACして次へ。
F - Coprime Solitaire
どうやっていいか全然わからない。でもこれはABC。「典型キーワードは何だ？」と何度も問う。フローと2-SATを思いつく。最小カットだと「違うグループにしたらダメ」を表現できるけど、この問題はなんか違うっぽいのでしばらく考えて諦める。2-SATはACLにあるけど使ったことがない。頑張って考えるが、「複数あったらダメ」の扱いがわからなかった。悔しい。
