AtCoder Beginner Contest 158 F - Removing Robots

ABC158-F問題です。公式解説とだいぶ違う方針だったので書き残したいと思います。

問題概要：

数直線上に$\ N\ $個のロボットがあり、$i\ $番目のロボットは座標$\ X_i\ $にいる。各ロボットは起動すると右に$\ D_i\ $だけ動く。他のロボットにぶつかるとそのロボットも起動する。移動を終えたロボットは取り除かれる。
高橋君は好きな回数ロボットを起動できる。数直線上に残るロボットの組み合わせは何通り考えられるか？
・$1 \leq N \leq 2 \times 10^5$
・$-10^9 \leq X_i \leq 10^9$
・$1 \leq D_i \leq 10^9$

ロボットを起動する順番は重要ではなさそうです。そこで座標の昇順に次のようなDPを考えたくなります。

$dp[i]\ :=\ $左から$\ i\ $番目のロボットまで見たときの組み合わせの総数

各ロボットについて、「そのロボットを起動するかしないか」の$\ 2\ $通りがあるので、このDPは単に総数が倍になっていくだけになってしまいます。しかし実際には、前のロボットの動き次第ではそのロボットは強制的に起動するので、これだけでは不十分とわかります。
では一つ前のロボットが起動したかどうかも状態に持てば良いのではないか、という発想になります。しかしこれでもまだ不十分で、もっと前のロボットに巻き込まれる場合もあります。
重要なのは前のロボットが動いたかどうかではなく、「一つ前のロボットまでで、最も右に来たロボットがどこまで来たのか」です。そう考えると、次のようなDPが浮かびます。

$dp[i][j]\ := \ $左から$\ i\ $番目のロボットまで見て、座標$\ j\ $までロボットが移動するような組み合わせの総数

座標は非常に大きな値を取りうるので、map(あるいはunordered_map)で管理することにします。
遷移がどうなるかを考えてみます。

・$j \leq X_{i+1}\ $の場合：ロボット$\ i+1\ $を起動するかしないか選べます。起動しない場合の右端は$\ X_{i+1},\ $する場合の右端は$\ X_{i+1} + D_{i+1}\ $です。
・$j > X_{i+1}\ $の場合：ロボット$\ i+1\ $は強制的に起動するので、右端は$\ max(j, X_{i+1} + D_{i+1})\ $です。

各ロボットについて$\ 3\ $通りの遷移しかなく、十分高速です。