TopCoder SRM 476 (Div 1)

TopCoder 参加記録

250リサブミットして終わったかと思ったorzorz
LayCurse先生、みょんみょんと一緒の部屋。

Result

108位 198.12 / Unopened / Opened


248.12
1撃墜0ミス


1592->1722


また550のあるセットかよー。

Easy

問題

アナグマがいて、それぞれ毎日食べるエサの量がhungry[i]で与えられる。
アナグマを複数匹飼うとき、それぞれのアナグマは(自分以外のアナグマの数)*greed[i]だけエサを食べる量が増える。


一日に入手できるエサの量が与えられるとき、最大何匹のアナグマを飼えるか求めよ。

試行錯誤

えーと、なんだこれ、アナグマをi匹飼うとして飼えるか二分探索？


あれ、でもアナグマ最大50匹だしループで順に見てけばいい気がする。
コード書いた。50匹のケースをテストしてみる。
時間0.01secで平気ぽい。送信。


提出後、等号を間違えていたことに気づく！！！
修正orz 240点ちょいから198点まで下がったお。もうだめぽ。

Medium

なんだこれ問題超なげえ。

問題

Nユニットからなる宇宙船があり、その中のいくつかが緊急脱出用通路でつながっている。
緊急脱出用通路は以下のような形式で与えられる。
(ユニットA) (ユニットB) (Aについているキャビンの数) (Bについているキャビンの数)各キャビンは一人乗りで、かつ使い捨てであり、A-Bの緊急脱出用通路のうちAの側に備えられているキャビンはBへ一人を一度輸送することしかできない。


また、各ユニットは最大一つの緊急脱出用通路のループに属する。
このとき、全てのユニットにK人がどのように分布していても、全員がユニット0に辿り着けるようにするために増設する必要があるキャビンの数の最小値を求めよ。

試行錯誤

え、むず……

各ユニットは最大一つのループにしか含まれないのか。
フロー？DP？それとも強連結成分分解とかだろうか。


いや、もっと簡単に解けそうだ。
ループがない場合、0を根にした木になるので、葉のユニットからK人が来られるようキャビンを増設するのが最適解。
ループがある場合、そのループを一つのユニットと見ると、上の場合に帰着する。
というわけで、ループ内でK人がどこにどう居ても脱出できるようにすればいい。


んで、それはどうするかというと、まずループには0のほうに繋がる脱出通路は一つしかない。何故なら各ユニットが属するループは最大一つだから。
で、ループの長さをMとでもしたら、最低増設数はそのループがどこで途切れるかをM通り試せばよい。


お、方針たった。書いてみよう。
……ループの検出が書けない。


あれやこれやデバッグしてるうちに終了。

Hard

Unopened.
だと思っていた時期が私にもありました。

Challenge

自分と同じケースの人いそう。あれでサンプル通るし。
いた。落とす。


もう一人いた！落と……そうとしたらケース入力中に他の人に落とされた。
くそー！！


あ、あれ？自分なんで550Unopnedになってるの？
……開いたの1000だった！！！！やたら難しいと思ったよ！！！


ほかに落とせるのはなく終了。

System Test

250通った。