ライブラリ

E - MUL ~燃やす埋める・最大流・フロー flow~

Quiz E - MUL https://atcoder.jp/contests/arc085/tasks/arc085_c AC Code https://atcoder.jp/contests/arc085/submissions/8316327 解法 アルメリアさんの解説の通り その他 割る・残すは右左のどちらでもいい(今回たまたまアルメリアさんとは逆になった…

C - 座圧 ~座標圧縮 (直接書き換えVER)~

Quiz https://atcoder.jp/contests/abc036/tasks/abc036_c 解法 座標圧縮(座圧と呼ばれる)をするだけ AC https://atcoder.jp/contests/abc036/submissions/8143705 code // 座標圧縮 // Aをそのまま書き換えるVER void compress(vector<ll>& A){ // 変換表 aut</ll>…

ワーシャルフロイド 参照用 (クラスVerは最下)

// 隣接行列 ll d[100][100]; int main(){ // input ll N, M; cin >> N >> M; // 隣接行列の初期値。infにする rep(i, N){ rep(j, N){ if(i!=j) d[i][j] = inf; } } // 距離データ入力 rep(i, M){ ll a, b, c; cin >> a >> b >> c; a--; b--; d[a][b] = c; d…

A - Connection and Disconnection ~ランレングス~(文字列ver, 数値ver)

Quiz https://atcoder.jp/contests/agc039/tasks/agc039_a AC Code https://atcoder.jp/contests/agc039/submissions/7879593 ランレングス圧縮 (復元はできない) // ランレングス // 例 s = "aabccc" => [2, 1, 3] VI run_length(string s){ char prev = s[…

BITを2つ使って範囲加算・範囲和 (区間加算・区間和) range add

注意 range add, range updateは区別しよう 今回はrange add 使った問題 C - Attack Survival https://atcoder.jp/contests/abc141/tasks/abc141_c Submisssion https://atcoder.jp/contests/abc141/submissions/7551683 できること 範囲加算 [a, b) にwを加…

スターリング数 stirling number (& ベル数 bell number)

意味 N人をKグループに分ける方法 AC (old, 漸化式埋めVER) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3786812#1 (new, memo) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4876088#1 読んだ(すごい) https://qiita.com/drken/item…

トポロジカルソート

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B AC Code http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3784044#1 関数化した。Code VI topological_sort(VV& G){ ll N = G.size(); // 入次数 VI IN(N, 0); rep(i, N){ fo…

N進数 7進数 変換 C++

ACコード https://yukicoder.me/submissions/352443 Code baseで割って余りを記録し、逆順に読む string change_base(ll a, ll base){ if(a==0) return "0"; stringstream ss; while(a){ ll rest = a%base; ss << rest; a /= base; } string s = ss.str(); r…

バブルソート

Quiz https://yukicoder.me/problems/no/397 ACコード https://yukicoder.me/submissions/351014 その他 バブルソートは関数化しておくと、今回のように交換したインデックスの組 (i, j) や、交換回数をカウントして反転数を求めるときに少し付け足すだけで…

最小全域木 MST (minimum spanning tree) O(ElogE)

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp Submission http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3589709#1 解法 Kruskal法を使う 同じグループ判定にUnion Findを使う エッジコストの小さい順に取り出…

ベルマンフォード bellman ford クラス実装

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B Submission http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3589692#1 参考 https://ei1333.github.io/luzhiled/snippets/graph/bellman-ford.html その他 競プロでの問題で…

重み付きUnion Find (Weighted Union Find Tree)

Quiz Weighted Union Find Trees http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B&lang=jp Submit http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3586483 学習 けんちょんさんの記事で学んだ https://qiita.com/drken/items/cce…

線分の交差判定 c++ Judgment of intersection of line segments

http://perogram.hateblo.jp/entry/abc016_4 この記事を関数として切り出した ※1番上のを安易に使うと誤判定する場合があります 関数(追記:❌) // 交差判定セット typedef complex<double> C; double cross(C a, C b){ return a.real() * b.imag() - a.imag() * b.</double>…

No.658 テトラナッチ数列 Hard 〜行列ライブラリのはじまり〜

Quiz https://yukicoder.me/problems/no/658 AC https://yukicoder.me/submissions/342366 解法 公式解説の通り コンパイル vector<vector > を初期化子リストで初期化するにはオプションが必要 g++ -std=c++11 answer.cpp その他 行列ライブラリと言えるほどではない</vector>…

累積和クラスを作ってみた

作成動機 元となる配列サイズ+1で作ったり、範囲の和を取る時に添え字でミスりそう いつも同じ作成をしているので省略したい Code struct AccSum{ vector<ll> Ac; ll L; AccSum(vector<ll> &A){ L = A.size(); Ac.resize(L+1); FOR(i, 0, L){ Ac[i+1] = Ac[i] + A[i]</ll></ll>…

素因数分解, 約数の種類数, 高速版 osa_k ~高速な素因数分解~

// 素因数分解 map<ll, ll> factorize(ll n){ map<ll, ll> mp; FOR(i, 2, n+1){ while(n%i==0){ mp[i]++; n/=i; } } return mp; } シンプルにできたので保存 計算量O(N) 別VER 上のはn=1010などではTLE https://yukicoder.me/submissions/335272 計算量O(√N) // 素因数分解 /</ll,></ll,>…

D - 閉路 abc014_4 ~木の深さを求めるdfs~

Quiz https://atcoder.jp/contests/abc014/tasks/abc014_4 Submit https://atcoder.jp/contests/abc014/submissions/4325911 根が0決め打ちなので注意 解法 どこかをrootにしてdfsでdepthを測っておく LCA (Lowest Common Ancestor)が高速に求まれば、depth…

LISとLCS D - トランプ挿入ソート (abc006_4)

LCS (Longest Common Subsequence) 文字列s, tの最長の共通部分を見つける naoyaさんの記事が分かりやすい http://d.hatena.ne.jp/naoya/20090328/1238251033 DPで解く // LCSセット const int S_LEN_MAX = 6000; ll dp[S_LEN_MAX][S_LEN_MAX]; ll LCS(strin…