ABC207

4完。ゴミ。

A - Repression

総和から最小値を引く。瞬殺できて嬉しい。

B - Hydrate

異常に難しい。不等式を解いてKの最小値を求める。C*D-B が正なら割って切り上げればいい。そうでないときは、そもそも最初のA個がなくてもD倍より多くなっているので-1を出力。

C - Many Segments

ハチャメチャに難しい。最初、共通部分を持つならばその共通部分は整数を含むと思ってしまいサンプルが合わず。そこで、入力を2倍して受け取ることで対応。AC。問題が難しすぎて何も考えてない。[l, r) の半開区間を基準として実装したが、これは一番左に寄ってるんだね。知らなかった。さすがに0.5の倍数は含むだろうと2倍にした。2区間の共通部分があるかどうかは、まず l の昇順になるようスワップしてから2番目の l と1番目の r を比較する。

D - Congruence Points

まず雑な解法として考えたのが、2点間の距離の集合を比較するもの(今考えると鏡にうつしたの判定できない)。三角形も考えるが、合同でも鏡にうつしたのはダメなので厳しそう。あとはSとTから1点ずつ固定し、それが対応する点であると仮定して他の点を偏角ソートし偏角と距離が一致するか調べる。さすがに想定ではなさそうと思い他の問題をやる。

他の問題があまりにも解けないので戻ってきて、結局偏角ソートをした。やってることは単純なのに、正確に書くのが難しい。つまらないことに時間を吸われて嫌な気持ちになる。まず、S側の点は一つに固定していい。T側でN通り試す。座標の値が小さいので偏角ソートは厳密にできる。引き算をしたら0以上2π未満に正規化。角度が同じものは距離でソート。これで、ぐるっと正規化された状態でソートできた。あとはN通り開始位置を試して完全一致判定するだけ。0番は基準点なので周期が N-1 であることに気づかず1WA。これは仕方ない。この方針はそのくらいきつい。

(解説を見て)重心は当然思いついていたが、N倍するだけで整数になるの気づかなかった(やれば気づくだろうけど方針をたくさん出して切り捨てる段階だとこうなる)。その後回転をN通り試すのも言われてみれば。差だけ見るやつもいいなあ。

E - Mod i

DPを考えていたが、どうしても3乗から落ちなかった。

F - Tree Patrolling

任意modのFFTでクソ重いlogを付けるのが3秒とはいえ想定ではないだろうと思いそちらへは行かなかった。