347.1

かなりひどいセット...。

250

三次元空間上を等速移動する二つの物体のパラメータが与えられるので、指定した距離以内に接近するか否かを答えよ、という問題。

距離は二次方程式で与えられて、下に凸なので三分探索...とやるとうまくいかないので、おとなしく二次方程式を解くだけ。

450

一回のジャンプで消費するエネルギーと飛距離の関係が与えられるので、目的値に到達するまでの最小エネルギーを答えよ、という問題。

結果的に下に凸になるので、三分探索するだけ。数式が凄く難読化された状態で与えられるのがポイント。

1000

電車で目的地に行きたいが、乗れる場所に到着するまで電車が正常運行かどうか分からない、という状況で移動時間の期待値を求めよ、という問題。

各種恣意的なパラメータ等もあって、そもそも期待値問題なのでDPするだけ。目的地までの残時間が分かっていないといけない方向のDPなので、目的地側からDPを開始する。開始点からメモ付き探索だとダイクストラに相当する作業が必要になるため、通らない。