Graph

AtCoder Regular Contest 084D: Small Multiple

https://beta.atcoder.jp/contests/arc084/tasks/arc084_biからi+1に移動する際、cost 1で、i*10に移動する際cost 0と考えてiのmodKのグラフで最短経路長を求めればいいです。 と言われると簡単だけど絶対本番思いつかない。解説に01bfsとかいうのが載ってい…

CF AIM Tech Round4C: Upgrading Tree

http://codeforces.com/contest/843/problem/C重心を根としてウニみたいなグラフを構成します。具体的な方法は http://kmjp.hatenablog.jp/entry/2017/09/05/0900 ここに書いてあります。 重心が複数個あるときもほとんど同じです。(複数といっても高々2つな…

CF434D: Wizard's Tour

http://codeforces.com/contest/860/problem/D解いたあとだとめっちゃ自明に見えるけどかなり苦労した。dfs木を作った後、2辺ずつ木の下からとっていく。 ある点vを中間の点としたpathがとれるときはとる。 取れない場合はvの親pに向かう辺(v,p)を残す。 そ…

Atcoder Grand Contest 019E: Shuffle and Swap (部分点)

http://agc019.contest.atcoder.jp/tasks/agc019_eaをS[i]=T[i]=1が成立している数 bをS[i]=1,T[i]=0が成立している数 cをS[i]=T[i]=1を満たす異なる二つのiについてswapを行った回数 としてdpを行う。 b=N-i-a+cが成立するので、O(N^3)で求められます。 1の…

POJ 2914: Minimum Cut

http://poj.org/problem?id=2914これもフローとはまた違った話。全域最小カット。Stoer–Wagnerを使う。Stoer–Wagnerは 「点の集合からの辺のコストの合計が大きいもの点から取っていって、最後から二番目に取った点sと最後に取った点tの最小カットは tから生…

POJ 3713: Transferring Sylla

Mengerの定理より全域最小点カットを求めれば良い。すべての点対に対してフローを流せばできるが、それではTLE。 全域最小辺カットならO(V^3)のアルゴリズム(Stoer-Wagner)が存在するが、全域最小点カットは見つけられなかった。全域最小点カットが2以上にな…

Codeforces Round #419C: Karen and Supermarket

http://codeforces.com/contest/815/problem/C3乗っぽいけど2乗な木dp。 5000*5000*2のlong longの配列持ったらMLEした。 さらに初期化を適当にやりすぎてO(N^3)になってしまった。 直してAC。 int N, B; vector<int> G[MAX_N]; int dp[MAX_N][MAX_N][2]; int dp2</int>…

Codeforces Round #423B: High Load

http://codeforces.com/contest/827/problem/B最初にrootを一つ決めて、あとはkコずつrootからまんべんなくつけていけば、木の高さが最小、かつその時の一番rootから離れているedgeの個数も最小になるのでこれが求めるグラフとなる。 int N, K; void solve()…

AtCoder Grand Contest 016E: Poor Turkeys

単調減少してから単調増加するPathがキーになることは分かったけど…ループがどうなるかよくわからなくなった。http://agc016.contest.atcoder.jp/tasks/agc016_eまずある一つの頂点xに注目する。操作を後ろから見て、i番目の人の操作が終わった際、何が生き…

AGC_016D: XOR Replace

http://agc016.contest.atcoder.jp/tasks/agc016_d うーん。Union Find見えてからが遅かった。EFもようわからん連結成分を考えれば良くて、変更前の数列のxorの値と変更後の数列のxorの値が等しいか異なるかで場合分け。 答えは(連結成分の数)+(異なる値の数…