Skip to content

改善できそうなもの #11

@toriitakuto

Description

@toriitakuto

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 さんより)内部関数を直書きにすると速くなりそう

それ以外の LC や ACLPC にあるものものについては,現在の最速の実装と見比べて大差ない(改善点があまりない)と思いました.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions