mayoko’s diary

プロコンとかいろいろ。

2016-02-22から1日間の記事一覧

2013 TCO Algorithm Round 2B easy: FruitTrees

問題 TopCoder Statistics - Problem Statement 解法 まず, りんごの木の位置は 0 に固定しても問題ないです。他の 2 つの初期位置を動かしましょう。これで O(n^2) みたいな感じになるので, あとは O(1) で木の最小距離 x を求められるようにしたいです。り…

Codeforces Round #343 (Div. 2) E. Famil Door and Roads

問題 www.codeforces.com 解法 kmjp さんの解法を参考にしました。kmjp.hatenablog.jpまず, この問題では 「グラフに辺を 1 本加えた時出来る閉路について, 特に u, v を含む閉路の平均長」を求める問題であることに注意します。depth[u] u, v の lca が u …

Codeforces Round #222 (Div. 1) C. Captains Mode

このこどふぉ, なんとなく DDPC 本戦が想起される(B が priority_queue を使ったほげで, C が高速化出来る dp) 問題 codeforces.com 解法 pick するなら, 残っているもののうち一番でかいのを取ってくるのが最適です。これを考えると, pick されるものとして…

Codeforces Round #222 (Div. 1) B. Preparing for the Contest

問題 codeforces.com 解法 二分探索します。check(x) = (担当する人が最大で x 日働いて良い場合の, 各問題の人の割り振りを表す配列。割り振れない時は ひとつ目の要素を -1 にする) とすると, 以下のようにすれば最小コストで担当者を割り振れます(前準備…

Codeforces Round #222 (Div. 1) A. Maze

問題 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)…