ABC076 D - AtCoder Express

問題
提出コード
終わってから解説を見たのですが、あまりよくわかりませんでした()

解法

実装系だと思います。
まず、加速度は、常に1v/secで増加or減少させて、さっさと目標の速度に直すほうが効率がいいです。
そして、入力がすべて整数なので、この時点で加速度を切り替えるタイミングは、0.5秒単位であることになります(こうなるのは、サンプル4のような、目標の速度に達していないけど切り替えなければならないケースのみです)。
あとは、0秒(スタート)から、最後までの速度を、0.5秒単位で調べます。
まず、全ての時刻について、そのときの速度制限で初期化をしておきます。
は、から秒の間の速度制限だとします。
このとき、から秒の区間以外でも、が影響をおよぼします。
というのも、から秒前だったとき、速度は最大でもしかだせません。同様に、から秒後だったとき、速度はしかだせません。
これを、すべてのについて行い、時刻がのときの速度を求めます。 先ほどの計算を行い、現状の最大速度との最小値で更新していけばよいです。最初と最後は速度が0になっていなければならないことも忘れないようにしましょう。
この更新が終わったら、走った距離を求めます。
秒のときの速度と、その0.5秒後の速度を足し、0.5をかけたあとに2で割ればよいです。
というのも、距離=速度×時間であり、台形(三角形)の面積、つまり(開始時刻の速度+終了時刻の速度)×(走った時間)/2によって求めることができるからです。
これをすべてのについて計算すれば、答えを求めることができます。
0.5秒ごとの速度を記録する場合は、全ての秒数を2倍してあげれば、全部が連続した整数になるので、配列で情報を記録してあげることができます。