前提 基本的な考えは、Bellman-Ford法による最小費用流の求め方と同じである。 以下の実装では高速化のためBellman-Ford法の実装個所をDijkstra法に置き換えており、同時に負の辺が存在するグラフに対してDijkstra法を適用するため、ポテンシャルを導入して…

前提 最小費用流問題のグラフには、最大流問題で与えられる辺の情報に加えて辺のコストが付与される。 以下の実装では、このコストに対してS-T最短路を1つ見つけて目いっぱい流す、その経路が限界になったら次の最短路を見つけて目いっぱい流して、という事…

前提 Dinic法を理解するには、先にFord-Fulkerson法を知っていると早い。 pione.hatenablog.com Dinic法の基本的な動作はFord-Fulkerson法と同じで、残余グラフを構築して増加路の辺、逆辺の capacity を更新していき、更新できるパスがなくなるまでそれを繰…

前提 最大流問題とは、辺に capacity を持つグラフが与えられて、始点から目いっぱい水を流した時に終点に流せる最大量を求める問題。 グラフの最大流は、そのグラフのS-T最小カットに対応する。 計算量: O(|flow||E|) （最大フローをflow、辺数をEとする） …

A(500) C1(750) E(2250) の3完。良問が多い回だった。 A - Shifting Stacks (500点) 英文読解の問題。 前の要素を自身より後ろの任意の場所に移動させられるという条件で、狭義単調増加を作れるかという問題。 B - Eastern Exhibition (1000点) 本番中にこれ…

問題 onlinejudge.u-aizu.ac.jp 前提 ダイクストラ法 クラスカル法 最近共通祖先（Lowest Common Ancestor） 解説 ダイクストラ法、クラスカル法（的な発想）、Lowest Common Ancestor、3つ基本アルゴリズムの合わせ技で解ける良問。 ざっと他の人の解説を見…

問題 atcoder.jp 前提 最長共通部分列問題（Longest Common Subsequence） 解説 最長共通部分列問題（Longest Common Subsequence）が解法の基盤になっていると思った。 LCSのDPでは、複数の列における部分列の長さの最大値を管理するが、この問題では不一致…

yukicoder.me 問題 1～nからn-1個を選んで作れる最小公倍数のうち、その最小値を求め、998244353で割った余りを求めよ。 前提 エラトステネスの篩 pione.hatenablog.com 解説 まず除外すべき1つの数は自明に、1～nの中の最大の素数である。 次にn-1個の数の…

一次合同式についての教育的な良問だったので、考えたことを書き残しておく。 問題 atcoder.jp 考えたこと この問題は言い換えると、初期値がsの状態からkを何度か足すことで、nの倍数を作れるか、という問題になる。 つまり、(kx+s)%n==0となる最小のxを求…

高難度帯の部分問題として出てくるので実装を置いておく。 実装 以下の実装は、訪れた順に頂点を採番していく。 /// オイラーツアー struct EulerianTrail{ vector<int> order; EulerianTrail(vector<vector<int>>& G, int root=0){ int n=G.size(); order.resize(n); int cur</vector<int></int>…

過去問埋めしてて、トポロジカルソートで解く問題に当たって面白かった↓。 atcoder.jp 良い機会なので、改めて実装についてまとめておこうと思う。 前提 トポロジカルソートとは、閉路無し有向グラフ(DAG)において、どの頂点もその出力辺の先の頂点より前に…

エラトステネスの篩と、それを利用した素因数の高速列挙の実装をライブラリ化した。（どちらかというと後者の実装を残す目的で作った） 前提 整数nまでの素数の列挙を高速に行うアルゴリズム O(nloglogn) https://mathtrain.jp/eratosthenes https://detail.…

前提 Trie木は、複数の単語（文字列）を登録でき、ある文字列（またはそのprefix）が登録済みであるかを高速に検索できるデータ構造 基本的な機能はシンプルに、insert / searchの2つだけ 実態は有向木 基本的な動作は、単語のprefixが同じならNodeを共有し…

二分探索と比べて、区間の内分点の取り方やら、下に凸か上に凸かやら、地味に考えることが多いので汎用性を目指してライブラリ化してみた。 前提 三分探索とは、ある区間[l, r]において、極値がただ一つだけ存在するとき、その極値の近似値を区間の長さをnと…

これは何 最近コンテストで、入力値が小数第4位程度まで与えられ、その入力値を素直にdoubleで受け取って計算すると丸め誤差で WA となるような問題が散見されるようになった。 （直近の問題だと ABC 191 D Circle Lattice Points がそう） atcoder.jp この…