Increasing Prefix XOR
https://atcoder.jp/contests/arc141/editorial/4048
と
を比較することで、答えの具体的な形を FPS を使って導出する。q-binomial coefficient と関係がある。
Stonks
https://atcoder.jp/contests/abc250/editorial/3945
離散凸解析の言葉で解法を機械的に導出。infimal convolution など。
Trespassing Takahashi
https://atcoder.jp/contests/abc250/editorial/3939
完全グラフの辺の重みが、別のグラフにおける距離になっているとき、その最小全域木は高速に計算できる。
Endless Walk
https://atcoder.jp/contests/abc245/editorial/3667
ゲームの後退解析やトポロジカルソートっぽい方法で閉路を検出。
Minimum Coloring
https://atcoder.jp/contests/abc231/editorial/3095
流量下限付きの最小費用流で、二部グラフの最小重み辺被覆を解く。
Bullion
https://atcoder.jp/contests/abc230/editorial/3036
ある種の分割統治 FFT を relaxed multiplication で定式化する。
Linear Probing
https://atcoder.jp/contests/abc228/editorial/2962
要素が で削除しかされない状況では、predecessor クエリが高速に処理できる。
Count Multiset
https://atcoder.jp/contests/abc221/editorial/2738
分割数の DP を工夫して、同じ数が 個を超えて出現できない分割を数え上げる。
Red and Blue Lamps
https://atcoder.jp/contests/abc218/editorial/2638
Monge グラフ上の 辺最短路。連続部分列に分解する問題で Alien's trick を使おうとすると Monge くらいしか凸性の保証ができないのではないかと思う。
Colorful Candies 2
https://atcoder.jp/contests/abc215/editorial/2531
多項式の Taylor Shift を使った数え上げの処理。
No Need
https://atcoder.jp/contests/abc056/editorial/2092
存在判定を数え上げにすることで戻す DP を可能にするテクニック。
ボディーガード (Bodyguard)
https://atcoder.jp/contests/joisc2021/editorial/1233
傾きではなく切片の方に単調性がある CHT の高速化。
