ABC076 D AtCoder Express

D AtCoder Express

所見

0.5秒ずつシミュレーションすればよいのはすぐにわかるが、1.次の区間の制限速度を守るよう減速できてもその次以降の区間の減速に間に合わない場合がある2.グラフの傾きが変わる際の最高速度の扱いを考える必要がある3.coutの出力で精度を指定しないと正解を出力しててもWAになる(ことがある)の3点で死ぬほどバグらせて終了した

問題概要

列車の運行時間をN個に区切り、それをt1...tNとする。各々の時間の最高速度をv1...vNとし、加速度は最大±1m/s²であるとき、列車が走れる最大距離を求めよ。

取った方針

サンプルケースを見ると0.5秒ずつシミュレーションすればいいような気がする。
次の区間の最高速度と今の速度があれば次の0.5秒を加速すべきか減速すべきかわかるので、t1+...tN秒間シミュレーションすればよい。
と思ったがこれは嘘で、ti秒間の区間について考えると、ti+1秒間の区間の最高速度のため減速できたとしてもti+2秒間の区間の最高速度までは減速できないパターンがある。
例

3
50 1  10
50 40 1

この場合、2番目の区間は1秒しかないため、この区間の最初に40m/sの速度を出していると3番目の区間の1m/sへの減速が間に合わない。

正しい方針(解説の方針)

一つの区間についてのみ考える。区間の左端をl秒、右端をr、その区間の最小値をvとおくと、時刻xの最大速度は以下のように表される。

0<= x <= l ならば v + (l-x)  
l<= x <= r ならば v  
x >= r ならば v + (x-r)  

これと最初と最後は0m/sであるという条件を組み合わせて考える。
これにより、各区間によって定まる各時刻の最大速度が求まる。
そのminが条件を満たすための各時刻の最大速度であるので、それを求める。
各時刻の最大速度が求まればそのグラフの面積を求めればよい。

得られた知見

・条件(今回の場合は最大速度を定める区間)がたくさん->それぞれ独立に考えられないか？を考える。考えられる場合問題が簡単になることがある。
・独立に考えた場合条件をどう連立するか？ AND？OR？その他？
・doubleを出力する場合はとりあえずsetpresisionをする。
・cout << fixed << setprecision(1000000) << ans << "\n";

解くのに必要な要素

・各区間の条件を独立に考えること
・シミュレーション

周辺調査によって得られた知見

特になし