cplib-cpp
cplib-cpp copied to clipboard
hitonanode
C++ competitive programming library
$O(N A_\mathrm{max})$ 復元つき https://atcoder.jp/contests/abc221/editorial/2741 https://stackoverflow.com/questions/18821453/bounded-knapsack-special-case-small-individual-item-weight-is-small-compared-t
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A&lang=ja を LP で定式化して、**双対をとった後で** simplex.hpp に投げると TLE になったり変な解が出たりする。多分退化対策が必要
- https://w.atwiki.jp/uwicoder/pages/2842.html - https://yosupo.hatenablog.com/entry/2021/01/31/160215 - https://nyaannyaan.github.io/library/string/suffix-automaton.hpp.html - https://cp-algorithms.com/string/suffix-automaton.html - https://pazzle1230.hatenablog.com/entry/2020/04/10/030325
http://dimacs.rutgers.edu/archive/Workshops/Tarjan/materials/talk-slides/goldberg.pdf https://compsciclub.ru/en/attachments/classes/slides_yZrxRpK4/graphalgorithms_lecture_030608.pdf https://www.cs.princeton.edu/courses/archive/fall06/cos528/handouts/Goldberg-Rao.pdf https://github.com/chasenorman/BinaryBlockingFlow/blob/main/goldberg_rao/algorithm.py
PQ-tree
https://codeforces.com/blog/entry/93018?#comment-820809 https://codeforces.com/contest/243/problem/E
LP が早いと色々捗る - 単体法 totally unimodular なら除算不要になる？ - 内点法 - 主双対内点法とかを実装してみたい - 自分で書かないに越したことはないので、OR-tools とかを使えないか検討
$O(N \log^2 N)$ $\mathbb{F}_p$ 上で実用上十分速いものはあるのだろうか？