最小費用流 Min Cost Flow 最大流の辺にコストがついたもので、ソースからシンクへある量のフローを流す時の各辺のフローとコストの積の総和を最小化する コストを損失と考えて最大化問題を解く考え方がよく使われる(こっちでそれを練習してからの方がいいか…

最大マッチング 色々な種類のマッチング問題があるが、大体調べれば多項式時間で解けるアルゴリズムがでてくる 二部最大マッチング 最大流問題に帰着できる（O(V^2E)かO(E*maxflow)） 二部グラフの最大マッチング＝最小頂点被覆 問題 二部グラフの被覆問題は…

最大流 Max flow 有向グラフで各辺ごとに流せる水の量が決まっていて、始点から終点まで最大どれだけの量流せるかを判定する 参考1 参考2 参考3 Dinic法はO(V^2E)、フォード・ファルカーソンではO(E*maxflow) 最大流を応用すると「二部マッチング」が解ける …

Div1 https://community.topcoder.com/stat?c=round_overview&rd=16883 Div1 Easy. ParenthesisRemoval ()から成る文字列が与えられる。 ()は良い文字列 X,Yが良い文字列ならばXYも良い文字列 Xが良い文字列ならば(X)も良い文字列 最も左の"("を1つ選んで、…

無向グラフ上で特殊な数え上げをする場合に使えるテク集 スペクトルグラフ理論 無向グラフをあるルールで行列に変換したものを使って色んな問題を解決する 参考1 参考2 ラプラシアン行列の固有値0の個数は無向グラフでの連結成分の個数と同じ 解説 行列木定…

http://agc014.contest.atcoder.jp【AGC014】コンテストは終了しました。ご参加ありがとうございました。解説PDF：https://t.co/9jlGEa5Dci解説放送：https://t.co/AT3kOEbKyo— AtCoder (@atcoder) 2017年5月6日以下、解説

http://yukicoder.me/contests/165以下、解説

LCA Lowest Common Ancestor 根付き木のある2頂点u,vの共通祖先で最も根から遠い頂点を高速に見つけること yukicoder上でのantaさんの解説 アルゴリズムはいくつかある「ダブリング」「HL分解」「RMQ使用」RMQが最速っぽいけど、体感HL分解の方が早いような……

https://www.hackerrank.com/contests/hourrank-20/challenges Hot and Cold 4人が部屋の温度の条件を言っている。 AさんはC[0]度以上がいい BさんはC[1]度以上がいい CさんはC[2]度以下がいい DさんはC[3]度以下がいい 4人の条件を満たす温度にできるか Cou…

https://www.hackerrank.com/contests/world-codesprint-10/challenges問題 Reward Points 1回スワイプすると10ポイント貯まる。 一ヶ月に最大100ポイント貯められる。 三ヶ月間のスワイプ回数が与えられるので、何ポイント貯まったか答えよ。 Zigzag Array …