面白い
問題
解法
一般性を失わず，\(A \leq B\)とする．
\(S_{i + 2} - S_i < A\)となる\(i\)が存在すれば答えは0．
次のようなDPを考える
\[
\begin{cases}
dp[i][0] = \text{\(S_i\)を\(X\)に振り分けるときの，\(S_i, \dots, S_N\)の振り分け方} \\
dp[i][1] = \text{\(S_i\)を\(Y\)に振り分けるときの，\(S_i, \dots, S_N\)の振り分け方}
\end{cases}
\]
なんでこのDPを考えたくなるかというと，\(S_i\)がどちらに振り分けられるか決めた時，そこから先のいくつかの要素はどちらに振り分けられるも決まるから．
もらうDPをする．
\(dp[i][0]\)への遷移は次のようになる．
\[
dp[i][0] = \begin{cases}
dp[i + 1][1] & \text{if } S_{i+1}-S_i < A \\
dp[i + 1][0] + dp[i + 1][1] & \text{otherwise}
\end{cases}
\]
\(dp[i][1]\)への遷移を考える ．
\(j\)を\(S_j - S_i \geq B\)となる最小のindexとする．これは二分探索で求められる．まあ尺取りでもできる．
このとき，\(S_{i+1}, \dots S_{j-1}\)はすべて\(X\)に入らなければならないが，\(S_{k+1} - S_k < A\)なる\(k\)が範囲に含まれているならこれは不可能．この判定は，隣接する数字との差分をセグメント木などで持っておくことで高速にできる．
もし可能なら，以下のように遷移する．
\[
dp[i][1] = \begin{cases}
dp[j][1] & \text{if } S_j-S_{j-1} < A \\
dp[j][0] + dp[j][1] & \text{otherwise}
\end{cases}
\]
最終的な答えは\(dp[0][0] + dp[0][1]\)．計算量は\(O(N\log N)\)
感想
最初，\(S_{i+1} - S_i < A\)となるところは一つ決めたら他も決まるからそれらをグループにしてDPしようとしていて，実装は大爆発するし見落としているケースも無限にあるという悲惨なことになっていた．グループにするのをやめて普通に一つ一つ見ていく感じでやったら驚くほど簡潔になった．こういう，変に工夫しようとしないでシンプルにやると実はうまく行くみたいなのに気付くのが遅いので強化していきたいところ．
