TopCoder SRM577

250

人々と自分の rating 一覧が与えられる。単純な規則に従ってランダムに SRM? の部屋割りを決める。自分の部屋の rating の平均値の期待値を求めよ。

自分の rating がすごい低い（最後に部屋に割り振られる）かそうでないか（そこでさらに自分の部屋の人数）で場合分け。面倒だった＞＜

500

8*8 の盤面に、いくつか小石を置く。小石を置くときには次で定めるコストがかかる：「新しく小石を置く位置から、すでに小石が置かれている位置までの Manhattan 距離の最大値」コストの和を最小化するときのコストを求めよ。

Manhattan 距離は扱いにくいが、よく知られているように (x, y) -> (x+y, x-y) の座標変換を実施すると 2 点の距離が「x, y 座標の差の絶対値のうち大きい方」で求められるようになる。
ここで、座標変換後に「すべての長方形領域の内部の小石たち」について最小コストを求める DP をすると、なぜか答えが出る（コストを求めるのに必要なのは、今まで置いた小石の x, y 座標の最小、最大値だけであり、さらにその間にある小石たちは後に置くよりも領域が小さい頃に置いたほうが明らかにコストが少ないから）。盤面がすごい小さいので多項式なら計算量ほとんど気にしなくてよい。

1000

盤面のいくつかのマスを黒く塗る。ただし、一度に黒く塗れるのは「縦または横に連続した白マスたち」だけである。目的の状態にするには最低何回塗る必要があるか。

50*50 とあるしどうせフローに極っているだろうと思って考えたが解けなかった＞＜フローの使い方がよくなかったらしい

結果

oox 597.14(7 位)
rating: 2697 -> 2783