ABC291に出た。

A: やるだけ

B: ソートして[N,4N)の平均

C: mapかなんかに通った場所を記録していけばよい

D: 最後に見たカードの表裏を持ってDP

E: 普通にキューを使ったトポロジカルソートをする、途中でキューに2つ以上の値が入っていたら一意ではないことが分かる

F: kを飛び越えるような移動路が存在して、かつその両端が1から到達可能な都市とNへ到達可能な都市かどうかを判定する。そのような移動路は最大で$O(M^2)$個存在するが、Mが小さいので$O(NM^2)$で通る。1とNの到達可能性は最初に1とNから距離を求めておけばよい。

各点が通れないときに～といった条件があるときに前計算で両側からの距離を見る典型。

G: 解けず。bit演算はビットごとに見れば畳み込みにできる。前にどっかで見たはずなのに思い浮かばかった。というかABCで畳み込み出ないだろという謎の思い込みがあった。畳み込みは普通に出る。

Ex: 解けず。重心という概念を知らなかったので仕方ないかもしれない。履修しておく。

知らない典型がまだまだたくさんあるので、この辺ざっと見ておくと良いかもしれない。

https://ikatakos.com/pot/programming_algorithm

クエリ平方分割、牛ゲーあたりは最近高度典型として履修したがまだ出くわしていない。もっと色々な高度典型を履修していけばどこかでエンカウントして役立つはず。