TopCoder SRM483 Div1

意味不明な問題セット←罠。

250

与えられた小数に最も近い分数を求めよ。分数の分子は上限が指定されている。「最も近い」とは、与えられた小数と、その分数を小数表記したものが、上の位からみてできるだけたくさん一致するようなものをいう。

やるだけ。通った

500

あなたは首相候補である。50人ぐらい人がいて、全員を自分に投票させたい。各人は抵抗値を持っている。ある人に賄賂を贈ると、ある影響値(fとする)だけその人の抵抗値が下がる。また、隣の人はf/2(小数以下切り捨て)、その隣の人はf/4(小数以下切り捨て)、…というように、隣の人達にも影響が伝わっていく。全員の抵抗値を0以下にすれば勝ちである。

貪欲法でやった人たちがたくさん落とされてるらしい。

この問題で重要なのは、影響値が500以下なので、i番目の人の抵抗値に影響を与えるのはi-8番目からi+8番目の人に限られる、ということ。
これを使えば、ビットDPで答えを求めることができる。でも実装面倒だったなー

900

羊たちを向こう岸まで移動させたい。移動には船を使う。羊たちはそれぞれ重さが決まっていて、船にも重量制限がある。船に乗せる羊を選ぶとき、残っている中で一番重い羊から使う貪欲法を用いる。船の移動回数に制限がある。船の重量制限はどれくらいにしたらいい？

二分探索安定ｗｗｗｗｗ

皆、そう信じていた。だから、900のSubmit率が非常に高かった。

しかしそれは大間違いで、船の重量制限を増やしたからといって移動回数が増えないとは限らないという罠が仕込まれていた！！！

結局全体で通してる人少ない（一桁）。解法わからない

結果

oox 469.6点 23位

Rating: 2088 -> 2214