ライブラリ

中国剰余定理 (CRT) 使いました記念

Quiz https://atcoder.jp/contests/acl1/tasks/acl1_b AC https://atcoder.jp/contests/acl1/submissions/17010040 解説ではなく、自分用の記録 drkenさんライブラリにより、「aで割ってb, cで割ってdになるようなxは?」という質問に答えられるようになった…

多角形の面積(凸じゃなくても可)は外積で求まる

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_A AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4868979#1 解説 https://imagingsolution.net/math/calc_n_point_area/ typedef complex<ld> C; // 外積 ld cross(C a, C b){</ld>…

点と線分の距離 ~long double VER~

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_D AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4868959#1 解説 点と直線の距離ではないので注意 点を線分に射影した後、射影された点が線分内にいるかもチェックした そ…

AOJ 2251 - Merry Christmas ~DAG上の最小パス被覆 minimum path cover~

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2251 AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4866924#1 解説 L個の条件について、条件iを実行後、条件jに遷移できるなら辺をはる。これはDAGになる そのDAG上の最小パス…

E - Sequence Sum ~サイクル検出(位置と長さ)~

Quiz https://atcoder.jp/contests/abc179/tasks/abc179_e AC https://atcoder.jp/contests/abc179/submissions/16895230 解説 Mが小さいので十分な長さの数列を作ればサイクルに入る Nが大きいが、サイクル分はまとめて処理できるのでO(M)となる ライブラリ…

D. Petya and Array ~座標圧縮してBITで数える~

Quiz https://codeforces.com/contest/1042/problem/D AC https://codeforces.com/contest/1042/submission/92543146 解法 editorialの通り、式変形して、leftを固定して条件を満たすrightを数える BITを用いて数え上げるために座標圧縮を使う(累積和を座標…

オイラーのトーシェント関数 (φ, ファイ, phi)

verified Same GCDs https://codeforces.com/contest/1295/problem/D AC https://codeforces.com/contest/1295/submission/92113264 AC(AOJ) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4869035#1 // 借り物 // https://ei1333.github.io/luzhil…

D. Maximum Distributed Tree 木DP, tree DP

Quiz https://codeforces.com/contest/1401/problem/D\ AC https://codeforces.com/contest/1401/submission/91696004 解法 辺の両端のノード数の積が大きい辺に、大きい値を割り振るといい 木DPで根からの深さと、部分木のサイズを求めておけばいい 「割り…

A. Marcin and Training Camp ~bitで見た時のsubset~ is_subset

is_subset /* b is subset of a a = 11001010 b = 01001000 => true */ bool is_subset(ll a, ll b){ ll c = (~b | a); if(c==~0LL){ // 11111111 return true; }else{ return false; } } A. Marcin and Training Camp Quiz https://codeforces.com/contest/…

Super Rolling Hash (自分用)

Superなロリハです 自分用なので説明はなし verified AGC47 B - First Second https://atcoder.jp/contests/agc047/submissions/15818636 multi rolling hash jupiroさんもやってたw https://atcoder.jp/contests/agc047/submissions/15784937

prefix palindrome (prefix function)

string rev(string s){ reverse(ALL(s)); return s; } string prefix_palindrome(const string& s){ VI pref(s.size()*2 + 10); string a = rev(s); a = s + "#" + a; ll c = 0; for (int i = 1; i < (int)a.size(); i++){ while (c != 0 && a[c] != a[i]) c…

BITを用いた転倒数(反転数)

// できること // 一点追加 // 範囲和 // ei1333's BIT struct BIT { VI data; BIT(ll sz) { data.assign(++sz, 0); } ll sum(ll k) { ll ret = 0; for(++k; k > 0; k -= k & -k) ret += data[k]; return (ret); } // [i, j] ll range_sum(ll i, ll j){ if(i…

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 E - MUL 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 ~ランレングス~(文字列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を加…

トポロジカルソート

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…