https://agc003.contest.atcoder.jp/tasks/agc003_f非連結だと勘違いしてハマってた…まず縦に並べても横に並べても繋がる場合は答えが1です。 どっちもつながらない場合は#の個数をPとしてP^(K-1)です。 問題は片方だけ繋がる場合です。今回は横に繋がるとし…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2382証明がむずい。地雷。絶対450じゃない。数オリメダリストの力を借りました。まず隣接してる頂点同士を結んで木を作ります。この木の辺の数をfとしましょう。 f=N-1の時、全ての頂点が直接的or…

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

https://beta.atcoder.jp/contests/arc097/tasks思考法を自分の中で確立して初めてのコンテストだったんですがうまくいったので舞い上がってます。C グッと睨むと5文字ずつとってsortすれば良いことがわかる。 D グラフにすればわかる。 E 条件がO(N)個あっ…

https://beta.atcoder.jp/contests/arc058/tasks/arc058_b コンビネーションやるだけだけど、素早く通せてよかった。 https://beta.atcoder.jp/contests/abc088/tasks/abc088_d 幅優先久しぶりに書いた… https://beta.atcoder.jp/contests/arc065/tasks/arc0…

https://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_fこれは特に言うことはなくて、合成する操作が木に見えて、木の高さが本質とわかれば解けますね。 int N; int B[MAX_N][2]; ll dp[MAX_N][2]; void solve() { cin >> N…

https://agc010.contest.atcoder.jp/tasks/agc010_fO(N)で心配になった…。まずある頂点vに対して、隣接している全ての頂点piに対してA[v] なぜなら高橋君がvからどこに動かしても、青木くんがvに駒を戻せばいいです。そうすればA[v]がいずれ0となり高橋君は…

https://agc009.contest.atcoder.jp/tasks/agc009_eまずK分木の葉に0や1を書き込んで、木の形状通りに平均を取っていく問題に言い換えます。するとK分木は葉が全て0の部分を除けば、縦1直線に繋げばいいことがわかります。 証明のアイディアとしては、葉が全…

https://agc018.contest.atcoder.jp/tasks/agc018_dアイディア自体はそこまで難しくないけど、証明がややこしいやつ。重心をとって、各子の部分木を渡り歩けば良いのかなぁという予想は簡単につくので、それが最善であることを頑張って示せばいいです。 ポイ…

https://dwacon2018-prelims.contest.atcoder.jp/tasks/dwacon2018_prelims_eこれはそんなに難しくない。重心分解して、一番部分木が大きい頂点から列挙します。 重心がsだとして、子が{a, b, c, d, e}だったとします。 そしたら(a,b)をまず聞いてaだったらa…

https://cf17-exhibition-open.contest.atcoder.jp/tasks/cf17_exhibition_a包除原理してpathを何本含むかでdpすれば良いということはわかりました。 ただ自信がなく解法見てやっぱり合ってたってなりました。 これ絶対debug時間かかるやつだと思いましたが…

https://beta.atcoder.jp/contests/arc088C A*2^nD 結構詰まった人もいるっぽい。端は好き勝手変えられるので真ん中だけ考えればいいです。AtCoder Regular Contest 080F: Prime Flip - omochan's diaryのように区間→2点更新の問題に言い換えられますが、今…

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

https://arc087.contest.atcoder.jp/C はい。 D XY独立にできます。 E 本質っぽいgrundyのところまではわかったけどtrie木で敗北しました。 まずstringを2分木に対応させます。そうするといろいろな高さの2分木から頂点を取るゲームになります。 高さがdの2…

https://arc086.contest.atcoder.jp/C ノーコメントD 符号を全部揃えれば簡単です。E（部分点) 木dpしただけ。満点解法はマージテクらしいです。 int N; int P[MAX_N]; vector<int> G[MAX_N]; int dep[MAX_N]; ll dp[2010][2010][2]; void loop(int v, int d) { d</int>…

http://codeforces.com/problemset/problem/852/E初全方位木DPです。観察するとGood Moodになる方法とBad Moodになる方法は同じ数だけあります。なのでGood Moodのみ考えれば良くて、 全方位木DPをすれば簡単に求められます。全方位木DPについてですが、これ…

http://codeforces.com/contest/875/problem/Fprinceを点、princessの二人のprinceの候補を辺とみます。それからkruskalっぽいことをします。具体的には 1.違う連結成分どおしで、二つともlockedじゃなければ繋ぐ。 2.同じ連結成分どおしで、lockedじゃなけ…

http://omochan.hatenablog.com/entry/2017/07/15/181512この問題で師匠のコードを見ていたら、Sparse Tableっぽいの使っているなあと思ったので僕も実装してみました。 vcost[v][k]:vから2^k個先の親までのpathで一番小さい辺のcostとすると、ダブリングと…

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

http://codeforces.com/contest/860/problem/EHL分解やるだけで通ってしまった… depthの浅い頂点から順番に見ていき、根まで+1をする更新を行うことで求められます。segtreeでやったら遅かったのでbitにして1824ms/2000msでAC。 struct BIT { //0-origin!!! …

Euler Tourは木を直線にして扱いやすくするテクニックです。 これを使うとLCA、二点間のpathの長さがO(logN)で求められます。でもHL分解ならあるpath上の辺の長さをすべて+1するみたいなこともできるので、汎用性はHL分解の方が上です。 HL分解は実装が重い…

http://agc014.contest.atcoder.jp/tasks/agc014_eマージテクの問題を一つ解きたくなったので。詳しくは解説に任せるが、青と赤の辺が重なっている部分を一つの頂点に併合していく感じの操作が出来れば良い。 これは各頂点から生えてる辺を持ってマージテク…

UVaデビューです。UVa Online Judge重心分解。問題はどうやってsubtree間のpathを高速に処理するか。 まず各subtreeの重心からのpathについてdamageとlengthの合計を求めておく。 それをすべて一つの配列に入れてsortして、その配列と同じ大きさのsegtreeに…

http://poj.org/problem?id=2114蟻本と同じことやるだけ…と思うがO(MNlog^2N)になって通るわけないだろ!と思い、ググってみるとどうやらそれでいけるらしいと分かったので、submitしてみるとTLE。途方に暮れているとvectorにstaticつけると速くなるよって書…

http://poj.org/problem?id=1741重心分解。解法は蟻本にある。適当に整備して使いやすいようにした。updateだけいじればよくなっている。updateも重心を根とする木について考えれば良いので楽。 namespace CD { //centroid decomposition struct edge { int …

http://arc078.contest.atcoder.jp/tasks/arc078_b解法自体は簡単だけど、バグらせたので。 こういう境界でバグらせやすい問題は[a b)の区間で考えるのがよさそう。 [a (a+b)/2)にすると半分、またはそれより1小さくなり、 [a (a+b+1)/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()…