上手く行ったように見えて上手く行かなかった参考記事 https://qiita.com/uk714/items/a3ee7407b928153113da https://qiita.com/k_maki/items/140f7c14482488891cf9 https://webkaru.net/clang/mingw-gcc-environments/ https://pavement1234.net/vscode_c_c…

ダイクストラ法 単一始点から全ての終点までの最短経路を求める ダイクストラの経路は木になる（最短経路木） https://snuke.hatenablog.com/entry/2021/02/22/102734ダイクストラの処理は一次元DPの応用と認識することが出来る 計算量は 計算量は天才でない…

グリッドをグラフに変換するコンストラクタ GT_GridGraph(ysize, xsize, exsize = 0): (ysize, xsize) のグリッドをグラフに変換（exsizeは超頂点の数） メンバ関数 Vertex(y, x): グリッド座標 (y, x) に対応する頂点インデックスを返す ExVertex(ll ex): …

Fenwick Tree (Binary Indexed Tree) 点加算クエリと区間合計取得クエリを で処理するメンバ関数 operator[i]: 要素[i]の値を取得 resize(size): sizeにリサイズする add(i, x): 要素[i]に値xを加算 sum(l, r): 半開区間[l, r)の合計を取得 関数詳細 T sum(l…

素数判定 任意の値 x が素数かどうか で求める #include <bits/stdc++.h> namespace NyaaLIB_NTL { namespace IsPrime { using ll = long long; auto is_prime = [&](ll x) -> bool { // x が素数か判定 O(√x) if (x <= 1) return false; for (ll i = 2; i * i <= x; i++) i</bits/stdc++.h>…

動的リスト ユニークな要素を扱うリストで要素の相対位置をO(1)で取得できる リストという名前を付けたけど、内部で使ってるデータ構造は unorderd_map 注意点: イテレータは存在しないので全要素を出力するときは下記のようにする DS_DynamicList<long long> dlist(LLO</long>…

静的リスト ユニークな要素を扱うリストで要素の絶対位置をO(1)で取得できる リストという名前を付けたけど、内部で使ってるデータ構造は deque と unorderd_map deque interface T& operator [](ll i): 値[i]を取得 O(1) T back(): 末尾要素（ end の1個前…

ランレングス圧縮 (Run Length Encoding) Run(seq): 列 seq をランレングス圧縮する 戻り値 struct RLE_RES cnt: 連続部分列集合の個数 x: 部分列の要素 size: 部分列の長さ sub: 部分列集合 range: 部分列と対応する列の半開区間 (0-index) #include <bits/stdc++.h> names</bits/stdc++.h>…

Strongly Connected Components（強連結成分分解）計算量 https://atcoder.github.io/ac-library/production/document_ja/scc.html run(void) 有向グラフを強連結成分分解する 戻り値 g: 強連結成分分解した隣接リスト groups: 閉路毎の頂点集合（トポロジカ…

BFS（幅優先探索）計算量 BFS開始頂点は複数になることも多いので配列を渡す 昇順に頂点を遷移したいときは queue を priority_queue にする std::queue<long long> q; → std::priority_queue<long long, std::vector<long long>, std::greater<long long>> pq; #include <bits/stdc++.h> namespace NyaaLIB { struct BFS_ARG { using</bits/stdc++.h></long></long></long>…