295.1

250

同じ大きさのカードを使って、カードが落ちないように少しずつ外側にせり出していくようにする。1枚目は半分だけ出せて、二枚目は1/4だけ出せて、三枚目は1/6だけ出せて...、という風になる。このとき、特定の量だけ外に出るには何枚必要か答えよ、という問題。

doubleでやっても精度が問題になることはないらしいので、単純に合計を取るだけ。

500

N個の入れ子の部屋について、各ドアが閉まる時間が与えられる。各部屋について、ある時間滞在すると、ある量の得点をもらえるとするとき、外に出られる状況で可能な最大のスコアを求めよ、という問題。

各ドアについて、自分が閉まる時間が外側のドアよりも後であっても意味がないので、外に出られる可能な時間に書き換える。後は、外に出られる部屋について、外に出られる範囲で滞在するかどうかを決めて、時間についてDPするだけ。

1000

二次元上の点を開始点として、規則に従って移動する。いくつかの終了点があるので、そこに到達する確率を求めよ、という問題。

開始点から探索していくと、精度が足りない感じ。終了点から確率を決定していくのでも終わらない感じ。手詰まり。

入力方向は4つで、分岐する可能性のある場所が開始点の他に10点。全部で200ちょっとくらいの状態からなる遷移グラフにできるので、200^3の行列乗算を収束するまでやれば良さそうな気もする。double精度なので100回くらいだとすると、終わらない。