ABC 076 D - AtCoder Express
解法
まず, サンプルをみると速度・時刻が0.5刻みで決まっていきそうなことがわかるので, 時刻・速度ともに２倍に引き伸ばします. これで多少は考えやすくなります.
前方向から順に速度を決めていくと, 減速しきれない区間が現れたりしてうまくいかないので, 到着する場所から, とりうる最大の速度をdpします.
(各区間ごとの最高速度)と(一秒後の最高速度+1)の小さい方が, とりうる最大の速度となるのでこれをすべての時刻について回します.
あとは, スタート地点からゴール地点までにおいて, 取りうる最大の速度について, 貪欲に加速しながら台形の面積を加算していくと答えが求まります.
時刻と速度を2倍に引き延ばしているので, 面積を4で割る必要があります.
感想
先に各時点での最大速度を求めるのは発想としては自然だと思います(思いつきませんが). しかし, 各時点での最大速度を求めるときに区間の境目においてはちょっと処理がややこしく, そこだけ分けて考えるとよいです. (
は
に含まれているため, 双方の速度制限を満たしている必要があります. )
