Skip to content

改善できそうなもの #11

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 にあるものものについては,現在の最速の実装と見比べて大差ない(改善点があまりない)と思いました.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

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