273.1

実装系セット。

250

丸い物を積むことを考える。下に何もなければ落ちる。そうでないなら、右下に何もなければそちらに落ちる。さらにそうでなければ左下に何もなければ落ちる。このとき、積むx座標が順番に与えられるので、最終的にどういう形状に積まれるか答えよ、という問題。

実装するだけ。x座標を少しだけ横にずらしておかないと、x=0のときに横にどんどんはみ出すので注意が必要。

500

1次元上で、ある地点から目的の地点に移動することを考える。途中いくつかの点を通過すると速度を倍にすることができる。このとき目的地に到達するまでの最短時間を答えよ、という問題。

取り敢えず出てくる点をすべてソートする。今までに到達した左端の点と右端の点、今どの点にいるか、の三つを覚えておいて、初期状態からダイクストラを回す。(実際には面倒だったので、Warshall-Floydにしてしまった。点数が高々50なので、50^3が50^4になるだけ。)

900

各ステップに上下左右に移動するロボットが二台ある。矩形の箱の中のどこかにそれぞれ配置されているとき、高々10ステップ移動する間に衝突が起こる確率を求めよ、という問題。箱の大きさは100x100程度。

当然ながら100^4は終わらないので、計算を削る必要がある。ロボットは高々左右に10マス、上下に10マスしか移動しないので、一方の位置を決定すると、その40x40の範囲(壁に応じて中心がずれる)にいるロボットしか衝突しない。これでも終わらなかったので、実際に移動する上限をそれぞれのロボットについて求めてやれば、10x10程度の範囲になることが分かる。後は100^2*10^2だけ衝突判定をやるだけ。