TopCoder Member SRM503

250

何枚か食パンがある。食パンはいくつかの種類があり、種類ごとにちょうどいい焼く時間が決まっている。それを超えると焼けすぎになるし、それに達しないとうまく焼けてないことになる。各焼けてないパンと焼けすぎパンに対して、焼いた時間が与えられる。各パンの種類について、1枚以上の焼けてないパンと焼けすぎパンが存在するとき、パンは最低何種類あるか。

DPで解いた。実はソートして3つ比較するだけで答えが出せるらしい

500

ある国に、都市と村がある。村はどの都市にも今は道路でつながっていないので、つなげたい。今、次の操作をすべての村が都市につながるまで繰り返す。「村をランダムに選び、その村から最も近い都市または都市につながってる村を選んで、道路を引く。同じ距離のがたくさんあるなら、適当に選ぶ。」道路の長さの総和の期待値を求めよ。

各村から、「すでに選ばれている中で最も長さが短いところへ結ぶ」という条件である。いくつかの村に対して、選ばれる順番がある順番になる確率は求められる。「最短のやつがすでに選ばれてる確率 * 最短のやつの距離 + 最短のやつが選ばれてなくて次に短いやつが選ばれてる確率 * 次に短いやつの距離 + …」として期待値が求められる。この確率は、注目している村だけに対して考えるとわりとすぐにわかる。

1000

２つの高いビルがある。ビルの各階には、非常口があったりなかったりする。非常口から階段をたどって地面まで辿りつけるようにしたい。階段の長さは√2の倍数でなければならないというか、横方向成分と縦方向成分の絶対値は等しい。また、「ある階から伸ばしていって、地面か他の階段にぶつかるまで作る」という規則で、任意の順番で作れる。階段の長さによって、建設費が異なる(短いといいわけではない)。すべての非常口から地面まで辿りつけるという条件下で、建設費を最小化せよ。

よくわからなかった。階段を「幹線」と「支線」に分けるとDPでいけそうな気がして実装したけど、バグってだめだった。

結果

なにも落とせなかった

oox 610.89 17位

Rating: 2558 -> 2629