有向グラフがDAGである場合は"Yes"を、閉路を含む場合は"No"を出力するコードです。DAGであるときは、xにトポロジカルソートの結果が入ります。していることはBFSですが、キューを使わないことでグラフの辿る順序を保存できています。面白いです。 #include <bits/stdc++.h></bits/stdc++.h>…

シンプルなダイクストラの実装です。 本質部分の実装はわずか14行で済んでいます。 #include <bits/stdc++.h> using namespace std; const long long INF = 1e18; struct Edge { int to, cost; Edge(int to, int cost) : to(to), cost(cost) {} }; int main() { int n, m; c</bits/stdc++.h>…

昇順にソートされたリストから任意の値のインデックスを取得したいことがある。 lower_bound()を使えばいいかもしれないけど、検索対象のデータ構造がvector<pair<int, int>>で、検索したいのがペアの1つ目の要素であるようなとき、lower_bound()を使う方法だと少しよくわか</pair<int,>…

遅延セグ木よりも定数倍速い。 遅延セグ木のコードの実行時間 : 1154ms 遅延セグ木部分だけをBITに置き換えたコードの実行時間 : 701ms 参考にしたページ Binary Indexed Tree のはなし - hos.ac verify済み Submission #70922924 - Codeforces struct Fenwi…

verify済み関数 for_each_edge : https://atcoder.jp/contests/abc133/submissions/10044047 lca : http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4170006#2 subtree_edge : http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4169995#2 for_e…

色々機能を追加する前の実装。 参考にしたページ http://beet-aizu.hatenablog.com/entry/2017/12/12/235950 https://codeforces.com/blog/entry/53170 struct HLD { vector<vector<int>> g; vector<int> vid; vector<int> head; HLD(vector<vector<int>> g) : g(g) { int n = g.size(); vid = </vector<int></int></int></vector<int>…

AtCoder Educational DP Contest T - Permutation こちらの問題の解法を理解したので書き残す。 …と思ったけど、言葉にできるほどきちんと理解していないことに気付いた。 とりあえず、中途半端な状態だけど書き残すことにする。 順列の位置を横軸、要素の値…

LCA LCAが思っていた以上に使えることがわかった。 重み付きの木で「ある頂点からある頂点までのコストを求めよ」という105個くらいのクエリに答えたいとき、別に全方位木DPを使わなくてもよくて、LCAで事足りる。 LCAの準備の過程で根からの深さも求まって…

検索される文字列をs、検索する文字列をtとおいたとき、次のようにループを書けばバグは発生しない。 for (int i = 0; i + t.size() <= s.size(); i++) { if (s.substr(i, t.size()) == t) { /* */ } } ポイントは半開区間[l, r)で考えること。 |S| = S.size…

次の3つのルールを守る。 キューに追加する直前に、まだ距離配列が更新されていないかをチェックする キューに追加するときに距離配列を更新する それ以外の場所で距離配列をチェックしたり、更新したりしない このルールを守ることで、シンプルかつバグの発…

問題 Convex-Hull Trickの入門に最適な問題。 DPの更新式を変形することでmin({ A[1]*x + B[1], ..., A[i]*x + B[i] })の形を得て、これはConvex-Hull Trickでの高速化を望める。

問題 初めて行列演算が腑に落ちた気がする。 行列演算を使うことで、ベクトルの各成分の入れ替えたり、ついでに成分の値を倍にしたりできる。この問題だと、位置を64要素を持つベクトルと見て、移動を64x64行列の演算と見なせる。 今回の問題の自然な解き方…

問題 蟻本の復習みたいな感じ。 まずはじめに思いつくDPは以下のようなもの。 DP定義 dp[i][j][k] = 真偽値 i : 解いた問題の数 j : 雪男くんの解いた問題の合計秒数 k : 雪女さんの解いた問題の合計秒数 初期値 dp[0][0][0] = true dp[i][j][k] = false (i …

次の問題を解いた。 yukicoder No.783 - 門松計画 問題 この問題の解説を見ることで、個数制限なしナップサックDPを使えるようになった。個数制限なしナップサックDPについて少し勘違いしていて、次の順序でDPをするものだと思っていた。 荷物1を可能な限り…

こちらの問題を解いたのだけど、証明がまだきちんとできないことに気付いた。 証明したいのは「既に食べるピザが決まっているとき、価格の降順でソートして前から有料→無料→有料→…のように買うのが最善」という命題。交互に食べることが最善だなんてどうやっ…

桁DPの基本形 auto digit = [](long long n, int x) { while (x - 1) n /= 10, x--; return n % 10; }; dp[0][0][0] = 1; rep(i, 20) rep(j, 2) rep(k, 2) rep(d, 10) { if (j == 0 && d > digit(N, 20 - i)) continue; int _i = i + 1; int _j = j == 0 && …

問題を作った 1以上N未満の整数のうち、数字が昇順になっているものはいくつあるか。たとえば159, 1124457889, 5などがこれに該当する。制約は1 <= N <= 10^18。 解説 遷移は以下の図。 状態数は10。遷移は、現在の状態の数字よりも選択した数字のほうが小さ…

オートマトンと桁DP 桁DPは以下の図でだいたい説明できる。 0埋めDP（今命名）は以下の図。 この2つのDPの状態は独立しているので積が取れる（以下の表のNは上限）。 桁DP 0埋めDP 意味 0 0 N = 0のときの0 0 1 N > 0のときのN 1 0 N > 0のときの0 1 1 0 < D …

遅延伝搬セグメント木（遅延評価セグメント木、遅延セグ木）の実装。 #include <bits/stdc++.h>とusing namespace std;があれば動く。 コンストラクタは6つの引数を取る。 要素の数 2つの範囲の値をマージした結果を返す関数 遅延させていた値を範囲の値に反映する関数。第</bits/stdc++.h>…

貪欲法には「小さい順に選ぶのが最善」みたいなのがよくある。 しかし、それが最善である根拠は特になくて、「自明」であったり「なんとなく」であったりする。 僕もこれまで「なんとなく正しそうだから」という理由で貪欲法を使うことがあった。しかしそれ…

文字列検索の計算量を減らしたいときに使われるアルゴリズムの一覧です。といっても、2019/07/29現在はローリングハッシュのみです。随時追加していきます。【2019/07/30追記】Z AlgorithmとKMP法と接尾辞配列の項目を追加しました。 文字列\(S\)に部分文字…

Link-Cut Treeについてのメモです。 回転操作を行っても、左右の位置関係の情報は失われない 最初は、回転操作を行うと左右の位置関係の情報は失われると思っていました。Link-Cut Treeの仕組みの理解を妨げていた最大の誤解です。平衡二分探索木で回転操作…

木DPを使って解ける問題には、以下のものがあります。 ある頂点から最も遠い頂点までの距離はいくつか ある頂点を根としたときの木の深さはいくつか これらの問題に共通していることは、「ある頂点」という文言が含まれていることです。頂点数を\(N\)とおい…

LCAを求める方法はいくつかありますが、今回はダブリングを使う方法とHL分解（Heavy Light Decomposition）を使う方法を紹介します。【追記】オイラーツアーを使う方法を追加しました。【追記】Link-Cut Treeを使う方法を追加しました。 ダブリングによる実…