Falling Balls | CS Academy #67

dp[i][d]
:= 「i番目の台からd∈{左, 右}に落ちたとき最後にボールが行き着くx座標」
とする。

iをyの昇順に決定することでこのDPを解ける。
よって、事前にソートしておくことで
i<=j ⇔ y[i]<=y[j]
とする。
台iの端dからボールが落ちたとする。
このとき、x[i][d]の座標でy[i]の直下にあるような台jを探す。
もしそのような台jが存在しないならば
そのボールはx[i][d]にそのまま落ちる。
台jが存在するならば、dp[j][0]またはdp[j][1]のいずれかになる。
j<iなのでdp[j][d']はすでに求まっているので
dp[i][d]もすぐに決まる。
問題は直下の台jを探すことにある。
f(i, x)
:= 「台iの直下で座標xにあるような台、ただし存在しないならば-1」
とする。
まず台が一つもない状態は f(0, x) = -1
次に、f(i+1, x) を f(i, x)から計算したい。
台iは台j(<i)より高い位置にあるか、同じ高さでもx座標が異なる。
台iがxl<=px<=xrに存在するならば
f(i+1, x) = i (xl<=px<=xr)
f(i+1, x) = f(i, x) (その他)
なので適切な
範囲更新とインデックスによる値の取得ができればよい。
Range Update Query などを使う。