2017-08-14から1日間の記事一覧

UVa 10245: The Closest Pair Problem

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 12161: Ironman Race in Treeland

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

POJ 2114: Boatherds

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

POJ 1741: Tree

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

POJ 3470: Wall

http://poj.org/problem?id=3470平面走査するだけのタイピングゲーなんだけど、TLEがかなり厳しい。AC率308/2036が物語っている。vectorを配列にするとかベタな高速化をしてもACに至らず…segtreeが重いのかな?TLE解法 struct T { pi v; T(pi v = pi(inf, -1)…