-
Notifications
You must be signed in to change notification settings - Fork 8
Open
Description
convolution
convolution の高速化について詳しいことは何も知らないが,Nyaan さんの実装がとりあえず速い.
dsu
leader を set で管理しているのが気になる(Leaders を取得したい場面は限定的なのでいらないと思う)
floor_sum
非再帰にすると,atcoder 環境上でのランダムテストで 10% 程度速くなる
max_flow
dfs を非再帰にすると速くなる
min_cost_flow
heapq の中身が tuple なので,一次元化すると速くなる
scc
LC の python 最速が速い.https://judge.yosupo.jp/submission/216433
ここの scc の実装は stack に tuple を突っ込んでるのが遅かったりするか?
segtree, lazysegtree
(Shirotsume さんより)内部関数を直書きにすると速くなりそう
- 内部関数を書き換える前:https://judge.yosupo.jp/submission/237802 (1132ms)
- 内部関数を書き換える後:https://judge.yosupo.jp/submission/237801 (1092ms)
それ以外の LC や ACLPC にあるものものについては,現在の最速の実装と見比べて大差ない(改善点があまりない)と思いました.
Reactions are currently unavailable
Metadata
Metadata
Assignees
Labels
No labels