Luzhiled's memo
簡潔に計算量の話がまとまってて便利なのでよく参照する
グラフ
オイラー路(Eulerian-Trail)
グリッド上の幅優先探索(Grid-BFS)
ハンガリアン法(Hungarian)
二部グラフの最大マッチング(Bipartite-Matching)
二部グラフの最大マッチング(Hopcroft-Karp)
二重辺連結成分分解(Two-Edge-Connected-Components)
二重頂点連結成分分解(Bi-Connected-Components)
全点対間最短路(Warshall-Floyd)
単一始点最短路(Bellman-Ford)
単一始点最短路(Dijkstra)
単一始点最短路(SPFA)
強連結成分分解(Strongly-Connected-Components)
彩色数(Chromatic-Number)
最大クリーク(Maximum-Clique)
最大流(Dinic)
最大流(Ford-Fulkerson)
最大流(Push-Relabel)
最大独立集合(Maximum-Independent-Set)
最小全域有向木(Chu-Liu/Edmond)
最小全域木(Borůvka)
最小全域木(Kruskal)
最小全域木(Prim)
最小費用流(Primal-Dual)
橋/関節点(LowLink)
データ構造
BIT(Binary-Indexed-Tree)
Link-Cut木 部分木クエリ(Link-Cut-Tree-Subtree)
Link-Cut木(Link-Cut-Tree)
ウェーブレット行列(Wavelet-Matrix)
スパーステーブル(Sparse-Table)
スライド区間の昇順k個の和(Priority-Sum-Structure)
セグメント木(Segment-Tree)
トライ木(Trie)
マージ可能ヒープ(Skew-Heap)
列の平方分割(Sqrt-Decomposition)
平衡二分探索木(RBST)
平衡二分探索木(Red-Black-Tree)
永続配列(Persistent-Array)
文字列
ローリングハッシュ(Rolling-Hash)
接尾辞配列(Suffix-Array)
最長共通接頭辞(Z-Algorithm)
複数文字列検索(Aho-Corasick)
木
HL分解(Heavy-Light-Decomposition)
全方位木DP(ReRooting)
最小共通祖先(Doubling-Lowest-Common-Ancestor)
木の直径(Tree-Diameter)
木の重心分解(Centroid-Decomposition)
根付き木に変換(Convert-Rooted-Tree)
数学
Mod-Int
べき乗(Mod-Pow)
オイラーのφ関数(Euler’s-Phi-Function)
オイラーのφ関数テーブル(Euler’s-Phi-Function-Table)
ベル数(Bell-Number)
ラグランジュ補間(Lagrange-Polynomial)
二項係数(Binomial)
二項係数テーブル(Binomial-Table)
任意mod畳み込み(Arbitrary-Mod-Convolution)
分割数(Partition)
分割数テーブル(Partition-Table)
商列挙(Quotient-Range)
第2種スターリング数(Stirling-Number-Of-The-Second-Kind)
約数列挙(Divisor)
素因数分解(Prime-Factor)
素数テーブル(Prime-Table)
素数判定(Is-Prime)
組合せ(Combination)
行列演算(Matrix)
進数変換(Convert-Base)
階乗(Factorial)
離散対数問題(Mod-Log)
高速フーリエ変換(Fast-Fourier-Transform)
動的計画法
スライド最小値(Slide-Min)
一次元累積和(Cumulative-Sum)
二次元累積和(Cumulative-Sum-2D)
個数制限付きナップサック(Knapsack-Limitations)
最大長方形(Largest-Rectangle)
最適二分探索木(Hu-Tucker)
最長増加部分列(Longest-Increasing-Subsequence)
メモ
その他
>辺の追加削除クエリがオフラインで与えられる場合は、Undo可能Union-Findを用いることで効率的に処理できる。
座標圧縮(Compress)
Related Pages
- →ambiguous_stagnation×曖昧な停滞×明確な対立×対立回避×broad_and_shallow_listening×ブロードリスニング×広聴×広くて浅い×協力の深さと広さのトレードオフ×civic_muscle×パレート改善×existing_vendor×どこへ行ったのかのトレーサビリティ×agency×主体性×出した声が結果に変わる回路×decidim×geoip×nuro光でシンガポールと誤認される×マイナンバーカード認証×政府の効率化×ideation×agile_doctrine×機会を発信なしで知ることはできない×ダブルダイヤモンド×jonathan_fox×ダイヤモンドサンドイッチ×acute×immune_response×ハイパーローカル×⿻_plurality_&_6pack.care×reverse_procurement×参加型アカウンタビリティ×茹でガエル×chronic×uncommon_ground×地方課題×慢性×シビック・カタリスト×manufactured_urgency×緊急性の創出×shared_urgency×anton_eklund+_2023×特定データで機能するのは一般データでより楽×sensemaker×openai/gpt-oss×再現可能でなければ正統性がない×クローズドなモデルにロックインされないようにする×モダリティ×不可知論的ツール×specific_individual_topics×entire_systemic_viewpoint×実装より理論×アジェンダ設定の権限を人々に開放する×d-agreeシステム×台湾詐欺防止法×詐欺犯罪危害防制條例×fchpa×dbrand×cortico×スピーチとリーチ×言論の自由×freedom_of_speech×stanford_online_deliberation_platform×deliberative_polling×habermas_machine×再現性×artificial_intelligence_in_deliberation:_the_ai_penalty_and_the_emergence_of_a_new_deliberative_divide×pvcアルゴリズム×defensive_technology×d/acc×防衛的な集約×デジタル民主主義2030_meetup_#3×leon_erichsen×qvは決定論的×collaborative_meeding×civic_mascle×返信ボタンがない×層化無作為抽出×sitra×kerrokantasi×digifinland×polis×voxit×borgerforslag×folketing×your_priorities×message_checker×cofacts×roost×uncommon_groundのプロパガンダ×metaculus×6-pack_of_care×効用×ケア×connections_between_indivisuals_as_first-class_objects×joan_tronto×symbioenesis×共生進化×エピステミック・セキュリティ×epistemic_security×policy_lab×nesta×bit×demos×私たちが共に何かを知ることができることに関する安全保障×変容型ファシリテーション×実装ではなく思想が大事×スーパーノート→
- →vitalik_buterin×メカニズム×アルゴリズム×インセンティブ×credible_neutrality_as_a_guiding_principle×メカニズムデザイン×メッセージ空間×配分関数×移転×インセンティブ整合性×メカニズムの定義×メカニズムデザイン(書籍)→
- →二分累乗法×モノイド的構造を見つけて二分累乗×うまい変形で除算を回避する×abundance_で殴る×素数の_abundance×tonelli-shanks_のアルゴリズム×ルジャンドル記号×平方剰余の相互法則×2_次体×有限体×フロベニウス写像×lehmer_のアルゴリズム×cipolla_のアルゴリズム×高速フーリエ変換×フェルマーの小定理×巡回群構造を用いた特殊な畳み込み×1_の_2^k_乗根_mod_p_を用いた畳み込み×ペル方程式×単項イデアル整域→
- →数え上げ×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→
- →dp×重み付き区間スケジューリング問題×連立1次方程式×最小カット×最大独立集合問題×二部グラフの最大マッチング×dilworthの定理×区間スケジューリング×貪欲法×区間スケジューリング問題×マトロイド×マトロイド交差×有向全域木×カラフル全域木×指数時間アルゴリズム入門→
- →帰着する力×小さい制約の問題×nが8前後の制約×Nが10~20前後の制約×n_が_30~40前後の制約×n_が_50前後の制約×n_が_300~500前後の制約×n_が_1000_前後の制約×小さな定数に注目×変数を一つ固定する×3つのものの真ん中を固定×行列の半分×xとyにわける×操作の不変量に注目×偶奇に注目×偶奇で場合わけ×操作の順番によらない×時間軸反転×元に戻せる操作×左右から累積積×等差数列の加算は差に注目×区間反転の合成はxor×grundy数×余事象を引く×k番目の数を二分探索×xorは繰り上がりのない足し算×xorは桁ごとに分割可能×45度回転×差の最小化は中央値×代表的なグラフで考察×木は二部グラフ×木の直径×最大化を二分探索で×選択肢が少ない方から貪欲×二次元座標を二部グラフにする×順序を有向グラフにする×凸関数の極値は三分探索×単調増加ならしゃくとり法×等比数列は剰余に注目×n進数は剰余に注目×括弧列は上り下り×競技プログラミングで解法を思いつくための典型的な考え方×keyence2020_d×abc152 f×agc026_c×arc060_a×joi2008ho_c×abc034d×abc138e×abc023d→
- →僕のatcoderの学び方(〜緑)×僕のatcoderの学び方(〜青)×ARC106×気づきの言語化×結晶化×変形テクニックに名前をつける×行列の半分×二項定理×足し算の順序の変更×概念のハンドル×テストできるスニペットライブラリ×UnionFind×mod Pでの組み合わせ×educational_dp_contest×動的計画法×atcoder_library_practice_contest×AtCoder Library×帰着する力×帰着訓練→
- →交叉半束×結合法則×交換法則×冪等性×セグメント木×スパーステーブルとセグメント木×最小共通祖先×オイラーツアー×range_minimum_query×2d_sparse_table×2d_range_minimum_query×スパーステーブル→
- →ホッケースティック恒等式×二項係数の公式×vandermondeの恒等式×巨大なnについての二項係数×形式的べき級数×ARC110D_FPS×oeis×重複組合せの畳み込み×arc110d_nonfps×arc110→
- →思考の結節点2019-10-14×知識の保存形式×知識の表現形式がアップデートされなければならない×知識の表現形式のアップデート×連想のストック×連想装置×レコメンド×検索×2-hop_link×連想×知識を編むプログラム×リンクサジェスト×過去の自分の書き物と今の思考の結合支援×類似文書検索×word2vec×gyazz×転置インデックスと指差し×文書は場所×指差し×文書が階層的×長さをパラメータにしたdf×接尾辞配列×scrapboxの良さ(その2)×抽象概念×メタファー×知性を高めるシステム×アイデアの干渉効果×類似度ベースではないレコメンド×レコメンドとscrapbox×明示的なブラケティング→
- →出現集中×ポアソン分布×df×idf×tf-idf×この文書を代表するキーワードらしさ×単語分割×sentencepiece×sentencepieceのユニグラム言語モデル×viterbiアルゴリズム×Suffix Array×キーワード抽出×接尾辞配列→
"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]