ライブラリ

popcount bitcount 関数 C++

int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } 参考 maroonrkさん https://atcoder.jp/contests/agc038/submissions/7633722?lang=ja

判別式・2点を通る直線・2次方程式の解(x1,x2)

タイトルにある3つを関数化した // 判別式 ll discriminant(ll a, ll b, ll c){ return b*b - 4*a*c; } // 2次方程式の解(x1, x2) pair<ld,ld> quadratic_equation(ll a, ll b, ll c){ ll D = discriminant(a,b,c); ld x1 = (-b-sqrt(D))/(2*a); ld x2 = (-b+sqrt(D</ld,ld>…

2次元imos (二次元いもす) ~yukicoder No.60 魔法少女~

Quiz https://yukicoder.me/problems/no/60 AC code https://yukicoder.me/submissions/443826 クラス化してみた struct Imos2D{ VV A; ll H,W; Imos2D(ll h, ll w){ H = h; W = w; A.resize(H, VI(W)); } // [(y0,x0), (y1,x1)] void add(ll y0, ll x0, ll …

Range Mindex Query (最小値とindexのペアを返すセグメント木)

Quiz https://yukicoder.me/problems/no/875 AC code https://yukicoder.me/submissions/442780 補足 クエリに答えるときに、min値を持つ場所のindexを返す必要がある だから min + index = mindex というタイトルなのだろう 遅延なしSegTreeは書いたことが…

幾何・円の交点 (2次元)

Quiz https://atcoder.jp/contests/abc157/tasks/abc157_f AC code https://atcoder.jp/contests/abc157/submissions/10485169 交点コードはここにある 解法 snukeさんの解説放送を見て、snukeさんの幾何コードを貼る https://www.youtube.com/watch?v=TdR81…

A - JJOOII (JJOOII) ~文字列のランレングス(文字情報あり)~

Quiz https://atcoder.jp/contests/joi2012ho/tasks/joi2012ho1 AC code https://atcoder.jp/contests/joi2012ho/submissions/10256473 解法 Oの連続数に注目する 例えばOOOがあったとき(連続したOが3個でその隣は違う文字)、レベル3しか作りえない レベル…

bfsのたたき台

bfsってやるだけなんだけど、これまで汎用化していなかった たたき台としてここに書いておく verified E - チーズ (Cheese) https://atcoder.jp/contests/joi2011yo/submissions/10254552 D - Grid Repainting https://atcoder.jp/contests/abc088/submissio…

K - 巨大企業 / Conglomerate ~LCA~

Quiz https://atcoder.jp/contests/past201912-open/tasks/past201912_k AC https://atcoder.jp/contests/past201912-open/submissions/9277571 解法 LCA Code // LCA set VV G; const int N_MAX = 150010; const int MAX_LOG_V = 20; ll depth[N_MAX] = {};…

編集距離 O(N^2) DP

Quiz https://yukicoder.me/problems/no/225 AC https://yukicoder.me/submissions/408789 解説 編集距離そのものの問題 int dp[1050][1050]; i : sのi文字目 j : tのj文字目 までを一致させるための最小コスト としてDPで解く。O(N2) Code // 編集距離 cons…

累積XOR, XORの性質

説明 累積XORとは、累積和と同じように事前計算しておくことで範囲のXORをO(1)で求める方法のこと XORの性質 a xor a = 0 a xor 0 = a 上記を利用すると、A = a xor b xor c xor d xor e の値を持っていて c xor d xor e の値が知りたいときは A xor a xor b…

D - 道路の老朽化対策について ~サイズ付きUnion Find~

Quiz https://atcoder.jp/contests/abc040/tasks/abc040_d AC (verified) https://atcoder.jp/contests/abc040/submissions/8891107 解説 editorialの通りですが、ポイントとしては「橋の構築」と「クエリ」を同じvectorに入れてyearでソートした後、yearの…

2次元累積和クラスを作成 (二次元累積和)

動機 1次元累積和クラスはよく使っているため 2次元累積和を使う問題と出会ったため Code // 2次元累積和 struct AccSum2D{ VV Ac; // accumulate ll W; ll H; AccSum2D(){} AccSum2D(VV &A){ H = A.size(); W = A[0].size(); Ac.resize(H+1, VI(W+1)); // i…

2次元BITクラス

参考 http://hos.ac/slides/20140319_bit.pdf Code #include<bits/stdc++.h> using namespace std; using ll = long long; using VI = vector<ll>; using VV = vector<VI>; #define FOR(i,a,b) for(ll i=(a);i<(b);++i) #define rep(i,b) FOR(i, 0, b) #define ALL(v) (v).begin(), </vi></ll></bits/stdc++.h>…

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

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

ワーシャルフロイド 参照用 (クラス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 ~ランレングス~

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つ使って範囲更新・範囲和 (区間更新・区間和)

使った問題 C - Attack Survival https://atcoder.jp/contests/abc141/tasks/abc141_c Submisssion https://atcoder.jp/contests/abc141/submissions/7551683 できること 範囲加算 [a, b) にwを加える 範囲和 [a, b)の和を求める (計算量 : それぞれlog(N)) …

トポロジカルソート

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…

バブルソート

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 この記事を関数として切り出した。 関数 // 交差判定セット typedef complex<double> C; double cross(C a, C b){ return a.real() * b.imag() - a.imag() * b.real(); } // ベクトル p0->p1, q0->q1 bool is_intersect(C</double>…

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

Quiz https://yukicoder.me/problems/no/658 Submit 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…