ライブラリ

最短ハミルトンパス

頂点数は17以下を想定 隣接行列を与えるとパスを返す関数 // ハミルトンパスが存在するなら返す // (無いなら空の配列を返す) // 入力 G : 隣接行列 (adjacency matrix) // 参考にした : by tatyam // atcoder.jp/contests/abc190/submissions/19761405 VI…

始点に戻らなくていい巡回セールスマン bitDP N=17 (それって最短ハミルトン路) abc190_e

Quiz E-Magical Ornament https://atcoder.jp/contests/abc190/tasks/abc190_e AC https://atcoder.jp/contests/abc190/submissions/19830501 解法 K<=17と小さいので訪れる順番を全て試すbitDPをしたい 石の数が105と多いが、注目すべき石は17個に抑えられ…

有向グラフのオイラー路・オイラー閉路判定関数

Quiz https://yukicoder.me/problems/no/1605 AC✅ https://yukicoder.me/submissions/679290 #include <atcoder/dsu> using namespace atcoder; // 忘れがち // (有向グラフ版) // オイラー路ライブラリ // そもそも連結されているか (by BFS) // 有向グラフなら始点に</atcoder/dsu>…

整数行列の掃き出し法の問題をけんちょんさんライブラリで解いた

Quiz 057 - Flip Flap(★6) AC https://atcoder.jp/contests/typical90/submissions/23287874 掃き出し法? 適用すると、行列が上三角行列( or 行階段行列?)になる(下記画像) けんちょんさんの記事 https://www.google.com/search?q=Gauss-Jordan+%E3%8…

橋・関節点・lowlink (自分用) O(N+M)

algo-logicさんのライブラリをお借りした https://algo-logic.info/bridge-lowlink/ 橋(と関節点)をO(N+M)で求められる(AC)ことを確認した 無向連結グラフにおいて、「取り除いたときにグラフ全体が非連結になるような辺」を橋と言います verify (AtCoder)…

01BFSクラスで解く、器物破壊高橋君

Quiz https://atcoder.jp/contests/arc005/tasks/arc005_3 AC https://atcoder.jp/contests/arc005/submissions/19891504 解説 問題としては01BFSやるだけ 構造体にまとめてみた struct ZeroOneBFS{ ll H,W; VS S; VV d; // distance const int dx[4] = {-1,…

全ての都市をそれぞれ1回は訪れる最小コスト(始点と終点は違ってよい, bit DP)を関数化した

Quiz E-Magical Ornament https://atcoder.jp/contests/abc190/tasks/abc190_e AC https://atcoder.jp/contests/abc190/submissions/19830501 感想 似たのが来たら貼るぞ! 距離行列やdpテーブルで未記入の-1やinfが混乱しがち 訪れたらフラグを上げるのか下…

POJ K-th Numberを通すまでに苦労したこと ~領域木(l,rの範囲にx以下の値は何個あるか)~

Quiz http://poj.org/problem?id=2104 POJ一般 auto使えない using使えない include bits使えない 苦労したこと 問題文の読み間違い。Aは負値もある cinではなくscanfを使わないとTLE(問題文に書いてある) scanfで読み込み先がintかlong longかで指定を変…

彩色数

グラフの彩色数問題とは、辺で結ばれた頂点は違う色で塗る時、最低何色必要かという問題 ei1333さんのライブラリを(引数を変更して)使いました記念 https://ei1333.github.io/luzhiled/snippets/graph/chromatic-number.html 計算量O(2N N) AC https://atc…

B. Marvolo Gaunt's Ring ~range min, range maxができる構造体で殴る~

Quiz https://codeforces.com/problemset/problem/855/B AC https://codeforces.com/contest/855/submission/100722877 解説 3つ組の真ん中を固定した時、左右でどれを選べばいいかは範囲min, 範囲maxが取れれば分かる 左からのmin, max配列 右からのmin, ma…

B. Unmerge ~部分和問題 subset sum~

Quiz https://codeforces.com/problemset/problem/1381/B AC https://codeforces.com/contest/1381/submission/99672317 補足 解説はeditorialの通り 部分和が実現できるか?のDPを関数化しておいた 計算量注意 O(N2) // 部分和問題 subset sum // 部分和でt…

連結判定 bfs

やるだけbfsはコピペで済ませよう 今回の設定では、地図が ##. #.. ... のようにドットが空地、#が壁として、空地が連結かを判定する ll H,W; int dx[4] = {-1, 0, 1, 0}; int dy[4] = { 0, 1, 0, -1}; bool in_range(ll i, ll j){ if(0<=i && i

C. Link Cut Centroids ~木の重心~

問題説明 重心が1つのみの木を作りたい。辺を1つ削除し、辺を1つ追加して新たな木としてよい時、それは可能。その操作(辺の追加・削除)を構築せよ Quiz https://codeforces.com/contest/1406/problem/C AC https://codeforces.com/contest/1406/submission…

D - Teleporter ~ダブリングで再AC~

Quiz https://atcoder.jp/contests/abc167/tasks/abc167_d AC https://atcoder.jp/contests/abc167/submissions/17244023 その他 コンテスト中は周期を使って解いたが、こういうワープ系はダブリングで捉えるとより一般的 ということで解き直したらかなり簡…

(コスト付き)木の直径(by dfs) 復元付き

yosupo judgeでAC https://judge.yosupo.jp/submission/25877 直径のパスも求められる // 木の直径(コストあり) struct TreeDiameter{ vector<vector<PII>> G; // (to, cost) ll N; ll start,end; VI path; ll d; VI TO; // 初期化のみ TreeDiameter(ll n){ N=n; G.res</vector<pii>…

中国人郵便配達問題 Chinese Postman Problem (CPP) bitDP ~全ての辺を1度は通って始点に戻る~

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_B AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4878657#1 解法 オイラー閉路にしたい(頂点の次数が全て偶数) これの「中国人郵便配達問題」を参考にした https://www.…

中国剰余定理 (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に遷移できるなら…

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 部分木のサイズ, 深さを求めるサンプル~

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なロリハ(ローリングハッシュ)です ロリハを2本持ってチェックを2回することで衝突リスクを減らして(?)います verified AGC47 B - First Second https://atcoder.jp/contests/agc047/submissions/15818636 multi rolling hash jupiroさんもやってたw…

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を用いた転倒数(反転数)O(N logN)

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

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>…