https://agc001.contest.atcoder.jp/tasks/agc001_fわりと自然な考察で解けるからそんな難しくはないけど…でもおもしろいのは確か。解説にあるとおりトポロジカル順を求めれば良いんですが以下はその具体的な方法です。 (i,A[i])のようにplotします。 [i,i+k…

https://beta.atcoder.jp/contests/arc101本番解けないと意味ないってそれ一番。 コンテスト中は1完です…C K個の連続した区間になるので適切に計算すればO(N)。 D 本番誤読してかなしぃ。中央値はやっぱりにぶたんなんだよなぁ。 https://agc006.contest.atc…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2021&lang=jpは?これも難しくないか? 普通にO(MN)頂点O(MN^2)辺のグラフでダイクストラすればいいんですが、これだと若干重くないか?ということで、O(N^3)解法にしました。Aから中継点を数カ所挟…

https://codeforces.com/contest/1019Aで無限に時間を使ってしまい、絶望的だったので撤退…いやでも今後のためにも提出したほうがよかったかなぁ…A 普通に勝たせる人に何票入れるかで全探索すれば良いんですが、いろいろこんがらがってしまいだめでした… B …

https://codeforces.com/contest/949ABしか解けないよぉ助けてくれA 最大のzebraを取っていけばいいことはわかりますが、実装にてこずりました。こういうのはsetって一番言われてる。 B 再帰的に求めていけばいいです。 C 最近有向グラフの問題といてなくて…

https://codeforces.com/contest/986AB397位 A bfsします。 B 3nと7n+1で偶奇違うのに気づくのにすごい時間かかってしまった…。 C こういうグラフの問題は初手をミスるとなんにもできなくなりますね…。 補助グラフを使ってうまくまとめる感じです。https://c…

https://agc015.contest.atcoder.jp/tasks/agc015_cこの発想に至るまでが時間かかる気がする。森の数=木の頂点数-木の辺数と言い換えられれば勝ちです。 あとは累積和適当に取れば通ります。実装なんですがB,S,E,U,D,L,Rと7つも2010*2010の配列を作ってしま…

https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_iだいぶ時間使ったけどなんとか解けました。良問です。順位表が求められればトーナメント上の順番は簡単に求まります。順位表上でi番目がj番目よりも小さくならなければならない条件をi->jに辺…

https://cf16-exhibition-final-open.contest.atcoder.jp/tasks/cf16_exhibition_final_e初手が難しい…。グラフの水の容量がB,水をやり取りする辺の距離の合計をA,都市の数をKとすると、なんと最大値は(B-A)/Kであることが証明できます。 Aは都市K個の最小全…

https://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_fこれは簡単だった。どんなグラフになるかというと、連結成分を潰して1つの頂点と見れば直線になっています。 なので、dp[i][j][k]:=(i回目でまだとっていない点の数がj個、1を含…

https://agc001.contest.atcoder.jp/tasks/agc001_dこれ知識的には誰でも解けるけど結構思考しないといけなくて面白い。同じにならないといけない文字同士を結ぶグラフを考えると、直線+ループになる。これは各点の次数が2以下であることから示せる。 なので…

http://codeforces.com/contest/909/problem/E全体的に問題文の把握に手間がかかっていますね…A はい。 B 親の顔より見た問題。一番重なっているところを累積和で求めます。 C 勘違いした… D 削除は奈良市計算量チャンスです。 E 問題を理解するのに無限に時…

https://arc083.contest.atcoder.jp/C 全通り試しましょうD とりあえず全部辺を張ってみて矛盾がないかワーシャルフロイド確かめましょう。矛盾があったら-1を返します。 もし矛盾がなかったら、頂点u,v,kについてdist(u,v)=dist(u,k)+dist(k,v)となっている…

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

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

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

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

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

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

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

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

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

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