TopCoder SRM486 Div1

300

いきなりぶっ飛んだ配点。
レジスタ1つで、+,-,*,/の処理しかできないコンピュータがある。それぞれの処理は、レジスタの内容を演算子の両側にぶち込んで実行してレジスタに戻す。プログラムは処理を書き並べたものである。ある値から、目標の値にするとき、最も短いプログラムを求めよ。同じ長さのものがあるときは、辞書順最小のものを出力せよ。

いきなり困惑させる問題。
目標->最初 に向かってBFS。通った

450

クイックソート。ランダムにピボットを選んで、「ピボットより左にあってピボットより大きい」「ピボットより右にあってピボットより大きい」ものの数＋再帰的に呼び出した時のそれぞれのコストが、あるクイックソートのコストになる。コストの期待値を求めよ。

「ある数以上ある数以下について行うときのコストの期待値」を持っといてDP。通った

1000

何個か点があって、バットマンとロビンが警備する。それぞれはある凸面を警備し、凸面が重なったり触れたりしてはいけないらしい。すべての点は、どちらかの警備凸面の中（もしくは周上）にないといけない。警備コストは、凸面の面積として表される。バットマンのコスト >= ロビンのコストじゃないといけない。バットマンのコストを最小化せよ。

点集合を適当な直線でぶった切って、それぞれの領域について凸包を計算し、面積の最大値をとったものを、いろいろな直線に対してやって、最小値を求める。その「いろいろな直線」がよくなかったみたいで落ちた。

結果

チャレンジはできなかった。

oox 231.32 + 378.24 + 0.0 = 591.56 78位

Rating: 2214 -> 2254