説明 使用例 verified 用語（閉路、ループ） 説明 問題 https://atcoder.jp/contests/abc357/tasks/abc357_e Functional Graphの問題だと見抜けた後は、連結成分ごとに分けて考えて、それぞれ閉路部分がどこか求めるなど、よく求める形がありそうなので再利…

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

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…

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

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

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

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…

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

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

やるだけ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

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

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

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

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

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

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 解説 点と直線の距離ではないので注意 点を線分に射影した後、射影された点が線分内にいるかもチェックした そ…

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に遷移できるなら…

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

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

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…

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

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

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…

// できること // 一点追加 // 範囲和 // 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…

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