282.1

ちょっと時間が空いたので...。昔にランダムサンプルでやったセット。何も進歩していないのね...。それにしてもつまらないセット。

250

2x2のタイルを敷き詰めることを考える。2x2の領域が複数個あり、部分的にに1x1のタイルが置かれている。このときタイルを切る最小の長さを答えよ、という問題。

タイルの形状は3種類。それぞれに必要な枚数を考え、2x2のタイルから切り出す方法をgreedyに計算して、残った分の埋め合わせをするだけ。本当にうまくいくのかどうか良く分からない。テストケースはかなり少なめ。

450

あるものが同じ重みの複数のものの集合で表現されるとき、あるもののM/Nの量を適切に表現せよ、という問題。

あるものがK個のものからなるとき1/Kずつ先頭から取っていく。取れない場合はM/N-X/Kだけ余っているなら、再帰的に計算して、そうでなければ終了する。

1050

1秒おきにドアのあいている確率が与えられ、目的地まで移動するのにかかる時間の期待値を答えよ、という問題。

確率とか期待値とか良く分かんない、の原因になってる問題のような気がする。基本的にはDPでテーブルを埋めるだけのはず。(あるいは収束するまで期待値テーブルを適当な規則で更新する。)

自分よりも期待値のいい隣接する部屋について、一つだけならそこへgreedyに移動するし、そうでなければ適当な評価値で都合のいい方に移動する。その評価式が謎。ドアのあいている確率から適当な比で求まりそうな気もする。