6完。しんどい問題が多いな。DEFに20分ずつくらいかけてる。Exも17分遅れで解けた。Gはわからない。
A - Growth Record
4分かかったんだが。青コーダーの俺様がratedコンテストでこんなんやらされるマジ？
X歳以上のときはTなので簡単。そうでないとき、M歳がX歳の何年前か求めて身長を戻す。実はNが関係ない。
B - Counterclockwise Rotation
これはいい問題。と思いつつ、きりみんちゃんのことを心配した。角度をラジアンに直す。360で割って2πを掛ける。πはacos(-1)で得られる。あとはcosとsinで回す。
C - XX to XXX
解法らしきものはすぐ見えるけど、詰めるのけっこう難しくない？ランレングスを貼って、構成と各文字が一致するかと長さを見る。長さ2以上なら今の長さ以上の好きな長さに変更できる。if文でそれの否定を書いたため、ちょっとわかりづらかった。長さが違ってて、S側の長さが1またはT側より長かったらダメ。
D - Circumferences
接することの検出と円が別の円に含まれる場合が怖い。図を描いて考える。2円の半径を足して中心同士の距離以上である必要がある。（含まれる場合を考えると）距離が半径の差以上である必要がある。これ差の絶対値でよさそう。懸念していた接することの検出は、距離の2乗で比較すればよかったので、絶対値をとるまでもなく2乗すればいい。なんかきれいに書けるけど意味があるのかな。2円の距離の2乗が、半径の和の2乗以下かつ半径の差の2乗以上。ついでにスタートとゴールの点も半径0の円として扱う。重なってたらUnionFindでまとめていく。
E - LCM on Whiteboard
最小公倍数というのは、同じpに対するeの最大値を集めたもの。数が小さければ両側から累積LCMなのでそのイメージに引きずられたが。1個だけ除くということだけど、それが影響するのは単独1位のeがあるときだけかつ単独1位が1個でもあれば（単独1位の素数が被ることはない（重要）ので）LCMが変わる（なんか感覚的に「こんなんでいいのか？」という感じだったが）。単独を検出するため2位まで保持するのは面倒なので、1位が何個あるかを持つことにした。unordered_mapで各素数に対しeの最大値とその個数を更新していく。全体のLCMを基準として、変化したら答えの変数をインクリメント。ただ、全体のLCMをどうカウントするかが難しい。実は、単独1位を持たない場合は全体のLCMと一致するので、出現したかを持っておいて普通にカウントできる。
F - Select Edges
マイナス使う意味ないよね。とか考えるが、これは木DPだ。部分木について余力を0か1以上残したときの最大を求める。問題はどの辺を選ぶかだが、選んだときにどれだけスコアが上がるか計算してソートして上から使うだけだった。特に負の重みを意識する必要もない。そこそこ腕力が要る実装で時間はかかったが、そんなに難しくはない。
G - Grid Card Game
コンテスト中は、まずGを考えて次に順位表を見てExと交互に考えてた。
ちょっと前にARC142Eをやっていたこともあり最小カットを考えるが、難しい。終了後、最小カットであるらしいことをツイートで見たが、それでも見えない。
（追記）たまに考えていたが全然わからない。考える気も起きない感じだったので解説をちょっと見て、あーやっぱり行と列の色を逆にするのかそこは行ってなかったなと思い、全カードから10^9点得るのをベースにペナルティかけてく方針で考えていたが重なった部分の処理がどうしてもできない。それで解説をもうちょっと読むと、書かれている整数が負かどうかで分けていて、まあそういうのありがちではあるけど状況を改善するとは思えないとか言ってたら-10^100点を上手く処理して何か解けててヤバすぎた。解けるような工夫をしていないように見えるのに解けている。まあ解けているので頑張って実装してAC。選んだ行や列全体、行でも列でも選ばれているカード、行でも列でも選ばれていないカード、といったものにたいするペナルティはかけることができる。選んだ行と列の重なる部分の負の数は禁止されているから考える必要がなく、一方選ばれなかったカードの正の数はペナかけることができる。そのように作られた問題なのだろうけど、構造が深すぎてコンテスト中に辿り着ける場所とは思えない。
Ex - Yet Another Path Counting
1種類のラベルについてなら、普通にDPできそう。ただ、たくさんのラベルについて並列にできたりしないかとか考えてもさすがに無理そう。終了後、平方分割を思いつき実装してた。個数がN以上のラベルは高々N種類しかないので、それぞれについてDPをしてもO(N^3)に収まる。個数がN個以下のラベルはペアを全探索してもO(N^2)で済むし、個数が多いほど不利そうだけどN個のものは高々N種類しかないのでO(N^3)で済みそう。各ペアについては、盤面が四角くて思ったより素直で二項係数やってくだけ。Exにしては簡単だ。
（追記）りんごさんがABCのadminやってるらしいけど、そうなると、こういう問題で非想定の正面から形式的冪級数とかで解く方法がもし存在していればりんごさんが発見しているだろうなという安心感がある。
