AtCoder Library
>様々なアルゴリズムを AtCoder 側で実装した
練習用コンテストで一通りACした解説
とりあえず確認してみたら1/3から1/2くらい既に実装してあった。今はリポジトリにバラバラに散らばってるので後でACLと同じディレクトリ構造にしてMITライセンスにしとこう。
残りの未実装なものは公式が「これは頻出アルゴリズムだ」と言ってるわけだからなるはやで実装する。
>AtCoder Library の Python 実装，普通にいろんなアルゴリズムを実装するとかはすでにいっぱいある（≒ yosupo judge や AOJ から取ってこればよい）はずだから，numpy/scipy/networkx とか cython とかでゴリゴリに高速化したものができてほしい src
Practice ContestのAll Submitの所要時間順ランキングがライブラリ速度を競い合う場になるのではないかと思ってる
内容
部分和の計算と要素の更新の両方を効率的に行える木構造(Binary Indexed Treeとも呼ばれる)
B: 600ms PyPy暫定一位
固定個数の要素がランダムアクセスで更新される時に総和や最小値をO(logN)で求めることができる木
文字列アルゴリズム詰め合わせ
752ms PyPy暫定一位
z_algorithm
数学アルゴリズム詰め合わせ
pow_mod
inv_mod
crt
畳み込み F - Convolution
Pythonだとnp.convolveとかに相当するやつ
Two Snukeではint64に収まらなくて自前でやった
Modint 自動でmodを取る構造体
Pythonだと演算子のオーバーロードで実現したら見た目は綺麗だけど、これを使うシチュエーションは関数呼び出しのオーバーヘッドを払えない状況だと思う
長整数が速いを使った攻略が良さそう
グラフ
無向グラフに対して、辺の追加、頂点が連結かの判定、をならし O(α(n)) 時間で処理
UnionFindってこと？
A: 277ms PyPy暫定一位
有向グラフを強連結成分分解
\bigvee (x_{i0} = v_{i0} \wedge x_{i1} = v_{i1})の形の論理式を充足する割当が存在するかを判定し、する場合にはその割当の一つを得る
ここで練習できる
Python関連記事
Related Pages
- →funding_the_commons_tokyo_2024×ftctokyo_day2×ftctokyo×国連大学×小池百合子@ftctokyo×funding_deeptech_and_decentralized_science_(panel)@ftctokyo×democratization_of_ai_and_social_implementation_using_web3@ftctokyo×innovation_implemented_by_public-private_co-creation×制約理論×under-use×社会的共通資本×寄付×social_common_capital×SCC×toc×ips細胞×再生医科学研究所×cira_foundation×食料の保存×交換様式a×plurality_in_japan(日本語)×見返りを期待しない贈与×the_role_of_emerging_technologies_in_japan’s_national_economic_strategy×ニセコパウダートークン×ニセコの早朝リフト券をnft化×nftによる地方創生×accepting_goodhart’s_law_in_academia×science,_technology,_and_citizenship×decentralizing_research_towards_“open_academia”×plurality質疑@ftctokyo×funding_the_commons×plurality×地方創生×web3×intersecting_group×今ここにあるplurality×今ここにある×glen+wbs×digdao→
- →数え上げ×degwer×状態をまとめる×dpは全探索の高速化×arc059f×codefestival_2016_final_f×aoj2439×探索順の変更×大きい順に並べる×aoj2333×順列は挿入dp×bit_dp×区間は終点でソート×条件の言い換え×操作は多いが産物は少ない×agc013d×線形和への分解×演算順序の変更×ビット演算を桁ごとに分解×部分群×操作が可逆で全域→部分群×ラグランジュの定理×再帰的定義→dp×arc037d×桁dp×aoj0570×累積和×フェニック木×高速フーリエ変換×ntt×高速ゼータ変換×and_と_add_の畳み込み×二分累乗×agc013e×行列木定理×全域木の個数×lgv公式×非交叉経路の個数×小さい確率を無視する×二項係数の公式×経路数×45度回転×xとyにわける×カタラン数×包除原理×agc005d×約数系包除×arc064f→
- →オイラー路×グリッド上の幅優先探索×ハンガリアン法×二部グラフの最大マッチング×二重辺連結成分分解×二重頂点連結成分分解×全点対間最短路×単一始点最短路×強連結成分分解×彩色数×最大クリーク×最大流×最大独立集合×最小全域有向木×最小全域木×最小流量制限付き最大流×最小費用流×橋/関節点×bit×binary-trie×convex-hull-trick-add-monotone×li-chao-tree×link-cut木_部分木クエリ×link-cut木×ウェーブレット行列×スパーステーブル×スライド区間の昇順k個の和×セグメント木×トライ木×マージ可能ヒープ×列の平方分割×平衡二分探索木×永続配列×素集合データ構造×UnionFind×ローリングハッシュ×接尾辞配列×最長共通接頭辞×最長回文×回文×複数文字列検索×hl分解×全方位木dp×最小共通祖先×木の直径×木の重心分解×根付き木に変換×mod-pow×オイラーのφ関数×オイラーのφ関数テーブル×ベル数×ラグランジュ補間×二項係数×二項係数テーブル×任意mod畳み込み×分割数×分割数テーブル×商列挙×形式的冪級数×形式的べき級数×拡張ユークリッドの互除法×拡張ユークリッド互除法×第2種スターリング数×約数列挙×素因数分解×素数テーブル×素数判定×組合せ×行列演算×進数変換×階乗×離散対数問題×高速フーリエ変換×divide-and-conquer-optimization×monotone-minima×スライド最小値×一次元累積和×二次元累積和×個数制限付きナップサック×最大長方形×最適二分探索木×最長増加部分列×ダブリング×包除原理×燃やす埋める問題×燃やす埋める×牛ゲー×mo’s_algorithm×offline-dynamic-connectivity×座標圧縮×アルゴリズム→
- →交叉半束×結合法則×交換法則×冪等性×セグメント木×スパーステーブルとセグメント木×最小共通祖先×オイラーツアー×range_minimum_query×2d_sparse_table×2d_range_minimum_query×スパーステーブル→
- →思考の結節点2019-10-14×知識の保存形式×知識の表現形式がアップデートされなければならない×知識の表現形式のアップデート×連想のストック×連想装置×レコメンド×検索×2-hop_link×連想×知識を編むプログラム×リンクサジェスト×過去の自分の書き物と今の思考の結合支援×類似文書検索×word2vec×gyazz×転置インデックスと指差し×文書は場所×指差し×文書が階層的×長さをパラメータにしたdf×接尾辞配列×scrapboxの良さ(その2)×抽象概念×メタファー×知性を高めるシステム×アイデアの干渉効果×類似度ベースではないレコメンド×レコメンドとscrapbox×明示的なブラケティング→
- →出現集中×ポアソン分布×df×idf×tf-idf×この文書を代表するキーワードらしさ×単語分割×sentencepiece×sentencepieceのユニグラム言語モデル×viterbiアルゴリズム×Suffix Array×キーワード抽出×接尾辞配列→
- →座標圧縮×setはメモリ食い×numba×numbaに複雑な型を渡す×numba bisect×numpy.unique×長方形グラフ探索×番兵×numba np.concatenate×csr_matrix×リンクトリスト×mprof×atcoder→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]