ABC 076 D - Atcoder Express

• 問題
• AC

1秒ずつシミュレーションしていくことを考える。1秒ごとに、可能なら速度を1上げ、無理なら速度を維持し、それも無理なら1下げるというロジックを書くことになる。判定する上での問題は、次の境界の速度制限$v_i$を達成することが可能だとしても、$v_{i+1}, v_{i+2}, ...$も達成できるとは限らないことである。これを考慮に入れるためには、実際に可能な速度の上限$v'_i$を末尾から求めていって$v_i$の代わりに使えば良い: $v'_{i} := \min(v_{i}, v'_{i+1}+t_{i})$。ただし$v'_{N+1}:=0$。

しかし、このままでは整数秒の中間で増減が切り替わるパターン（入出力例4）を扱えない。そこで、$(t_i)$と$(v_i)$を最初からすべて2倍して求まった距離を4で割ることにする。

……という考察自体はすぐに終わったのだが、実装の段階で境界条件をひたすらにバグらせてしまった。ACした後も、何がポイントなのかいまいちわからない。後でほかの人のコードを読む。