SRM610 Div2 Hard MiningGoldEasy
問題
TopCoder Statistics - Problem Statement
解法
xとyを独立に考える。
任意の動き方に対してx,yのそれぞれに対して座標の変化が起こらないような区間を考える。 すると関数 は のうちのどれかを最小値としてとるような凸関数であるので、 event_i、event_jに含まれるような座標の組み合わせに対する動き方のみ考えればよい。
よって座標圧縮してDPすればよい。
コード
証明が本質?
Codeforces Round 381 Div2 D Alyona and a tree
ダブリングでそれぞれの頂点がどこまで支配されるのかを求めた後、各頂点に+1, -1を記録し木上でimos法みたいなことをします。 O(Nlog(n))
gist2622f3016f0d316048b64712fa3894dc
500msくらいかかっていて結構遅い
はじめに
プログラミングとかについて書くかもしれません