cplib-cpp

cplib-cpp copied to clipboard

数ヶ月に一回使いたくなる（最近見たのだと https://yukicoder.me/problems/no/2654 など： 中央値との差の絶対値の平均 or 総和（Average absolute deviation のひとつ？）を求める）

hitonanode

Monge の d 辺最短路

1

https://noshi91.github.io/algorithm-encyclopedia/d-edge-shortest-path-monge ### 問題 https://atcoder.jp/contests/tupc2022/tasks/tupc2022_k https://codeforces.com/contest/1832/problem/F https://atcoder.jp/contests/abc218/tasks/abc218_h https://atcoder.jp/contests/abc305/tasks/abc305_h ### 関連 [簡易版 LARSCH Algorithm - noshi91のメモ](https://noshi91.hatenablog.com/entry/2023/02/18/005856) [Aliens DP で辺の本数が区間で指定される場合 - noshi91のメモ](https://noshi91.hatenablog.com/entry/2022/01/13/001217) [Aliens DP における二分探索の色々 - noshi91のメモ](https://noshi91.hatenablog.com/entry/2023/11/20/052227)

hitonanode

https://math314.hateblo.jp/entry/2016/12/19/005919 https://mojashi.hatenablog.com/entry/2017/07/17/155520 https://yukicoder.me/problems/no/2606 https://yukicoder.me/problems/no/263

hitonanode

https://codeforces.com/blog/entry/98376 - https://codeforces.com/gym/361606/submission/238849350 - https://yukicoder.me/problems/no/2589

hitonanode

BIT O(n) init

1

Tested: https://atcoder.jp/contests/practice2/submissions/45974331

alantudyk

https://twitter.com/noshi91/status/1383110660796518401 https://atcoder.jp/contests/abc319/submissions/45420835 ```cpp struct ComplementGraphBFS { int n; std::vector g; ComplementGraphBFS(int n_, const std::vector &edges) : n(n_), g(n) { for (auto [u, v] : edges) { g.at(u).push_back(v); g.at(v).push_back(u); } }...

hitonanode

FFT の回数を削って高速化できる https://web.archive.org/web/20220903140644/https://opt-cp.com/fps-fast-algorithms/

hitonanode

折れ線の下側を通る経路数

1

- 分割統治で解ける - https://onlinejudge.u-aizu.ac.jp/beta/room.html#HUPC2023Day1/problems/L - [Aizu Online Judge Arena](https://onlinejudge.u-aizu.ac.jp/beta/review.html#HUPC2023Day1/7762994) - https://codeforces.com/contest/1770/problem/G - [Submission #204608856 - Codeforces](https://codeforces.com/contest/1770/submission/204608856) - 「2 つの折れ線に挟まれた範囲」でも解ける - https://twitter.com/noshi91/status/1639645059997126656

hitonanode

完全永続セグメント木

1

https://qoj.ac/contest/1221/problem/6400 で必要になった気がする？

hitonanode

Sparsity matroid （疎性マトロイド）

2

$(k, l) -$ 疎性マトロイド（無向グラフの辺集合 $E$ の独立性の定義：任意の $\emptyset \neq F \subset E$ について $|F| \le k |V(F)| - l$ が成立）は以下の一般化になっている： - グラフマトロイド - Bicircular matroid [Bicircular matroid - Wikipedia](https://en.wikipedia.org/wiki/Bicircular_matroid) - 剛性マトロイド...

hitonanode