2016-02-22から1日間の記事一覧
問題 TopCoder Statistics - Problem Statement 解法 まず, りんごの木の位置は 0 に固定しても問題ないです。他の 2 つの初期位置を動かしましょう。これで O(n^2) みたいな感じになるので, あとは O(1) で木の最小距離 x を求められるようにしたいです。り…
問題 www.codeforces.com 解法 kmjp さんの解法を参考にしました。kmjp.hatenablog.jpまず, この問題では 「グラフに辺を 1 本加えた時出来る閉路について, 特に u, v を含む閉路の平均長」を求める問題であることに注意します。depth[u] u, v の lca が u …
このこどふぉ, なんとなく DDPC 本戦が想起される(B が priority_queue を使ったほげで, C が高速化出来る dp) 問題 codeforces.com 解法 pick するなら, 残っているもののうち一番でかいのを取ってくるのが最適です。これを考えると, pick されるものとして…
問題 codeforces.com 解法 二分探索します。check(x) = (担当する人が最大で x 日働いて良い場合の, 各問題の人の割り振りを表す配列。割り振れない時は ひとつ目の要素を -1 にする) とすると, 以下のようにすれば最小コストで担当者を割り振れます(前準備…
問題 codeforces.com 解法 まず空いてるマスのすべてを 'X' にし, 'X' となっている好きな点から幅優先探索して '.' を広げていけば良いです。 string field[505]; bool done[505][505]; int n, m, k; int main() { cin.tie(0); ios::sync_with_stdio(false)…