2完3ペナ。順当すぎて何もない。それで水パフォなのは落ち込む。
A - Toasts for Breakfast Party
まず、（問題の見た目からしてそうだけど）乗ってるトーストが0枚の皿はないとしていい。2枚乗ってるのから持ってくれば アンバランス度が下がるので。あとは、1枚のやつは美味しさのでかいやつにしたいし、残りは大きいのと小さいのを組み合わせたい。これはどの2枚のトーストを入れ替えてもよくならなそうだし、よりよい手段も思いつかない。これが通らないなら300点じゃないと思い提出。AC。
B - Product of Divisors
まず素因数分解する。約数に各素因数が合計で何個含まれるか考える。A^B=Π(p_i)^((k_i)*b) みたいになるから、0から最大までの個数の和に自分のとこ以外の(k_i)*b+1通りを掛けて求まる（998244353の倍数が現れても掛け算だけなので大丈夫）。あとは必要な個数で割ればいい（切り捨て）。その最小値が答え。実験するとなぜかどの素因数に対しても同じになる。出力させて調べてもよくわからないので提出する。ペナで時間を買う、あわよくばACを狙う、ARCらしい立ち回り。ここで、intをllにし忘れている2箇所で2WAしたのが痛すぎた。3個目のWAでようやく間違っていることがわかり、そこから考えるとなぜか同じになっていた理由がわかった。t*(t+1)/2としていたので気づかなかったが、ここに自分とこの(k_i)*b+1が入っていて、結局全部の積にBを掛けて2で割って切り捨てたものが答えになる。つまり、Bが奇数かつ(k_i)+1が全て奇数のときだけ1を引いてから2で割ればいい。
最初からちゃんと考えればいいんだけど、本当に見えないんだよね。もやもやしていて、コンテスト中の時間では考えきれない。今になってみても、「ああしていればよかった」と思うことがない。
C - MST on Line++
順位表を見てCDを両方読んだ。Dをメインでやっていた。
D - Good Permutation
閉路にひげが生えてるやつで「スワップとは何か」を考えていたが、そうじゃなくて閉路がいくつかあるやつだった。であれば、どこでもスワップするだけで2つの閉路が1つになる。順列を前から見て、自分より右で自分より小さいやつとスワップできるなら一番小さいやつとするというのでいけそう。各閉路に番号を付けそこに所属するインデックスをvectorで持ち、相手となる値たちをstd::setで持ち、位置の逆引きができるvectorを持ち、これでできなくもない気がする。が、そういうのが足りない、辞書順で大きくなるスワップをせざるを得ないケースもある。それが必要になったら後ろから同じようにやればいいか？それでいいとしても実装がきつい。
