Hatena::Grouptopcoder

blu_rayの日記

2011-09-18

Codeforces Beta Round #87 Div2

| 23:56

oo---

A. Tram / Accepted / 492

回すだけ。

B. Little Pigs and Wolves / Accepted / 530

ぱっと見は二部マッチングだけど、

It is guaranteed that there will be at most one wolf adjacent to any little pig.

任意の豚に対し、隣接する狼は多くても1匹という制約があるから、グリッド内の豚に着目して隣接する狼と一緒に消していき、数えていけば解けるのだけど、この文章に気づくまでかなり掛かって提出がかなり遅れた。それまでずっと最大マッチングの問題だと思って四苦八苦してた。。Editorialにも、最大流(はオーバーキルですよ)を仄めかすような文章がちらほら。

自分がアルゴリズムとか書き方について知っていれば、最適解でないにしろもっと早く提出できたので、蟻本見ながら勉強して二部マッチング版も書いてみた。。

C. Party

適当に書く -> TLE -> Editorial

一番深い木の深さなのか。

確かに最も深い木の深さだけグループは必要になるし、その深さをkとすると、他のノードと比較して、最も深い木の部分木は確実にグループ数k+1で足りるし、部分木じゃなくても深さkより大きくないから結局k+1で足りることになる。

D. Lawnmower

移動する行の一つ下の行を見ればいいのかな。

rate := 1336 -> 1296

提出が遅れて順位がやばかったため