ランレングス圧縮 (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>…

【木のDAG】 木に単一の方向性を持たせるとDAGになる 割り振り直した頂点IDは降順あるいは昇順になる このようなDAGは木でもあるので元の頂点IDはユニークでもある 頂点の割り振り直し方法 ・DAGの最長経路＝木の根からの深さ＝末端からMAXのBFS、で頂点IDを…

フィボナッチ数列の計算（メモ化再帰のテンプレートとしても使える） #include <bits/stdc++.h> using namespace std; using ll = long long; using vl = vector<ll>; auto mf = [&](auto self, ll now, vl& memo, ll inf) -> void { if (now == 1 || now == 2) { // 末端は定数</ll></bits/stdc++.h>…

ウェーブレット行列 任意区間のK番目の要素を高速に取得するデータ構造 https://ei1333.github.io/library/structure/wavelet/wavelet-matrix.cpp.html前計算 クエリ WaveletMatrix(v): 各要素の高さ v を初期値として構築する. access(k): k 番目の要素を返…

写像12相ライブラリ ただし写像12相以外の組み合わせ計算も含む Pow(x, n): 繰り返し二乗法 P(n, r): 順列 C(n, r): 組み合わせ H(n, r): 重複組み合わせ IEP(n, r): 包除原理 Stirling(n, r): 第二種スターリング数 Catalan(n): カタラン数 #include <bits/stdc++.h> names</bits/stdc++.h>…

クラスカル法 重み付き連結グラフの最小全域木を求める 引数 ARG_Kruskal n: 頂点数 g: 重み付き隣接リスト 戻り値 最小全域木となる辺 {from, to, cost} の集合を返す 依存クラス DS_UnionFind https://9871225.hatenablog.com/entry/2022/03/02/202403 #in…

Union Find DS_UnionFind(n): 半開区間[0,n) のデータ構造を確保 以下で処理できる関数 Union(x, y): xとyを結合 Find(x): xの根を返す Max(x): xが属する集合の最大値を取得 Min(x): xが属する集合の最小値を取得 Same(x, y): xとyが同じ集合どうか判定 Siz…

template<class T1, class T2>static mint Pow(T1 x, T2 n) 繰り返し二乗法で を計算する 計算量 namespace LIB { template<long long mod>class ModINT { using mint=ModINT; using ll=long long; ll inv(ll a, ll m) { ll b=m,u=1,v=0; while(b) { ll t=a/b; a-=t*b,swap(a,b); u-=t*v,swap(u,</long></class>…

深さ優先探索のテンプレート 引数の頂点変数について、大雑把な方針としては 頂点インデックスが不要なとき→頂点の値 vx 陽にグラフを持つとき→頂点インデックス vi 複雑な状態を持つとき→必要な状態全部 状態のオーバーヘッドが大きいときは参照渡しにして…

ゲーム系の最善手は逆算 木のDFSだが「間違えて元の局面に戻る」ようなDFSが絶対に発生しないので根への遷移かどうかのチェックは不要 問題文を誤読しないよう注意、直大さんのスコアは「マス[i][j] = o かつ マス[i][j] = マス[i+1][j]」でなく単純に「マス…

LCAライブラリ 木の最近共通祖先 (Lowest Common Ancestor) 前処理 することで以下のクエリに で答える Ancestor(x, y): 木頂点 (x, y) に対する最近共通祖先 Dist(x, y): 全頂点対間距離（任意の2頂点 (x, y) 間の距離） IsOnPath(x, y, z): x-y パス上に頂…

選択肢の少ない状態から考察すると楽 後ろから考えると値を流用できる https://atcoder.jp/contests/soundhound2018-summer-qual/submissions/25168114 0日目から考えると全ての都市で両替できるので最善を考えるのが大変だが n-1 日目なら選択肢は1通りしか…

https://atcoder.jp/contests/abc210/submissions/24941318最小全域木にクラスカル法というアルゴリズムがある。クラスカル法は「全ての頂点が連結になるまでコスト昇順に辺を選択してく」アルゴリズムだが、頂点と辺の数が多いため愚直にクラスカル法は使え…

足し算と引き算は順序関係ないので足し算と引き算の回数に着目して探索できる https://atcoder.jp/contests/agc017/submissions/24762083ABCD が なので N の線形処理と予想する。例えば A=10 で C=1, D=5 のとき＋すると区間 [11, 15] まで表現できる。更に…

欲張りマルチセット multiset に標準コンテナの頻出関数を全部実装した欲張りデータ構造 色々なコンテナを使い分けて処理する操作毎に関数名を使い分けるのが面倒な人にオススメ（適当） 内部に unordered_map を持つことで count(x) を定数時間に高速化する…

の種類数が2個以下でないとNoというのは自明なので の種類数を基準に場合分け 条件が多く大変だがサンプルが豊富なので、ある程度サンプルから条件を整理できる https://atcoder.jp/contests/agc016/submissions/24577904自分と同じ色が存在しない猫を「uniq…

遅延評価セグメント木 (Lazy Segment Tree) 任意区間のクエリを計算量 で処理するhttps://betrue12.hateblo.jp/entry/2020/09/22/194541 https://atcoder.github.io/ac-library/production/document_ja/lazysegtree.html https://betrue12.hateblo.jp/entry/…

N=32 は半分全列挙 https://atcoder.jp/contests/arc017/submissions/24169529ナップサック問題っぽい文章なのでナップサックDPではないと予想する（ぇ そもそも X が なので DP で処理するのは無理と分かる。 ここで N が 32 しかないことから半分全列挙し…

BIT (Binary Indexed Tree) 要素加算 、区間総和取得 https://atcoder.github.io/ac-library/production/document_ja/fenwicktree.html Fenwick Tree とも呼ばれる。遅延セグ木の下位互換だが、遅延セグ木に比べて定数倍高速に動作する。 namespace NyaaLIB …

頂点を増やすことでmodの遷移を判定する https://atcoder.jp/contests/abc132/submissions/24017041 愚直な考察をすると頂点に移動回数のmod情報を持たせたくなるが、実装が複雑で難しいので逆転の発想をする。具体的には頂点を増やすことで、modの情報を持…

二次元いもす法 矩形区間加算処理O(1)、矩形区間総和取得処理O(1)、更新処理O(HW) #include <bits/stdc++.h> namespace NyaaLIB { /** * 二次元いもす法 * 矩形区間加算処理O(1)、矩形区間総和取得処理O(1)、更新処理O(HW) **/ template <class T = int64_t> struct DS_NyaaImos2D { int64_t ys</class></bits/stdc++.h>…

型 primitive using ll=long long; using ld=long double; using bo=bool; using ch=char; using st=string; using bi=bitset<1>; using ull=unsigned long long; container template<class T>using ve=vector<T>; template<class T>using de=deque<T>; template<class T>using se=set<T>; vector</t></class></t></class></t></class>…

LIB::Imos 区間加算 、区間和取得 、更新処理 https://imoz.jp/algorithms/imos_method.html 累積和の機能を持つので累積和の上位互換として使える。 単純な累積和だと値の更新はできないが、このライブラリは任意のタイミングで値の更新が出来る。 メンバ関…

graph 深さ優先探索 auto dfs https://9871225.hatenablog.com/entry/2021/11/25/232020 ダイクストラ法（単一始点最短経路） auto dijkstra LIB::Dijkstra 単一始点から全ての終点までの最短経路を求める https://9871225.hatenablog.com/entry/2022/05/22/…

https://atcoder.jp/contests/agc018/submissions/23809861 最大の状態から減らすには何を減らせばよいか考える 最大の状態から始めて小さくするには「最大の要素を取り除くしかない」という貪欲 数字を変化させるには「少なくとも貪欲するしかない」なら貪…

https://atcoder.jp/contests/zone2021/submissions/23283470 辺の張り方とコストが特殊なとき、辺の数を減らして同値な移動を再現可能 コストを増やしたい→階層化して辺を追加すれば再現可能 上下左右1マス移動しかないなら単純にダイクストラ法をするだけ…

https://atcoder.jp/contests/abc203/submissions/23082310 小さい数を-1、大きい数を+1、としてカウントすると線形処理で中央値かどうか判別可能 中央値を求めるデータ構造として2個の priority_queue を持つ のアルゴリズムがあり、スライドウィンドウして…

https://atcoder.jp/contests/abc165/submissions/22916768 回転するので生徒を円状に配置して考察する 向かい合った頂点に辺を貼ると距離が異なるので被りづらくなる 偶奇で場合分け サンプル２がヒントであり、生徒を並べたとき距離の異なる数字同士でペア…