A 作業の合計回数は一定です。 B 勉強になりました。数が埋まってる区間がありそうだからそれをずっと探そうと思っていたけど、冷静になるとこれは十分条件から攻めているのであまり良い戦略とは言えませんね。やっぱり「ありえない」ものを除去していって、…

https://colopl2018-final-open.contest.atcoder.jp/A オンサイトだとこれでも詰まるよねぇ…端が繋がる時注意。B スタックでO(N)。再帰やってTLEするの普段絶対やらないと思うし、怖いね。C 一次式にしてもよくわからなかったので分割統治でやった。これ解け…

http://codeforces.com/problemset/problem/868/F良問of良問だと思う。まず簡単なdpから考えて、dp(i,j):=j番目までの数列をiコに分割した時の最小コスト、と定義すれば dp(i,j)=min(dp(i-1,j')+cost(j',j1))でできます。この時dp(i,j)が最小値となるj'をp(j…

https://community.topcoder.com/stat?c=round_overview&er=5&rd=16081Easy まずブロックがないとわかっているところを除外します。 あっても良いブロックで連結成分が何個かできたとします。 この連結成分を同時に2個取ることはできません。また各連結成分…

UVa Online Judge蟻本にO(NlogN)になる理由などは述べられている。実装だが、ここが本当にうまいと思った。 //a is sorted by x coordinate int m = n / 2; double x = a[m].fst; double d = min(closest_pair(a, m), closest_pair(a + m, n - m)); inplace_…

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 …

3185 http://poj.org/problem?id=3185普通に端から反転させるだけ…と思ったが、端の場合分けで反転の回数カウントしていなくてWA生やしまくった。1222 http://poj.org/problem?id=1222これも端を決めて反転するだけ。反転は決めることが本質。2100 http://po…