AGC009-C:Division into two - 思考の墓場

きれいな問題だなあと思った。

問題

解法

　簡単のため $A\lt B$ とする。逆のときはswapしても問題ない。こんなのdpしかないやろという見た目がするので，dpを考える。制約を無視すれば，今何番目の数を見てるかということと， $X$ または $Y$ に最後に振り分けた数はどれだったかということが必要に見える。そこで $dp_{i.j}$ を「 $i$ 番目まで振り分け済みで，最後に $Y$ に振り分けた番号が $j$ のときの振り分け方の総数」とできる。遷移は，① $S_i-S_{i-1}\geq A$ なら $dp_{i-1,j}$ から $dp_{i,j}$ に遷移できる。また， $S_0 = -\infty$ として， $0\leq j \leq i-1$ について，② $S_i-S_j\geq B$ かつ， $j+1$ から $i$ の間の $2$ 項間の差がすべて $A$ 以上であるときに， $dp_{i-1,j}$ から $dp_{i,i}$ に遷移できる。(なぜ $j+1$ からかというと， $S_j-S_{j+1}\lt A$ でも， $S_j$ を $Y$ に振り分けているから， $j+1$ は $X$ に振り分ければ問題ないからである。)もちろんこれを愚直にやると $O(N^3)$ で，到底間に合わない。
　よく考える。まず，「 $j$ から $i$ の間の $2$ 項間の差がすべて $A$ 以上である」かということをdpの更新のときに逐一調べる必要はない。つまり， $S_i-S_{i-1}\lt A$ であれば， $S_{i-1}$ より手前の数は，これ以降②タイプの遷移が不可能だとわかるので，そういう番号を管理する変数を持っておけばよい。これを $id$ とし，定義を「現時点で②のタイプの遷移が可能な番号の最小値」とする。さらに， $S_i-S_j\geq B$ をみたす最大の $j$ を二分探索し，それを $s$ とすると， $dp_{i,j}$ に遷移してくるのは $j$ の $2$ つ目の添え字が $id$ から $s$ までの数である。だから，累積和を取っておけば②のタイプの遷移は $O(\log N)$ で可能である。
　タイプ①の遷移だが，これは $1$ つ目の添え字が $1$ 増えるだけである。タイプ②の遷移も， $1$ つの目の添え字は $1$ 増えるだけだから，結局 $dp_i$ を「最後に $Y$ に振り分けた数の番号が $i$ であるときの振り分け方の総数」として，これを $i$ が小さい順に埋めれば十分である。最後に，明らかに答えが $0$ になるパターンの存在に気を付けよう。それは，ある $i$ が存在して $S_i-S_{i-2}\lt A$ となることである。 $S_{i-1}$ を $X$ にも $Y$ にも振り分けることができなくなるからだ。
　以上より，次のようにすればよい。

$S_i-S_{i-2}\lt A$ となる $i$ があったら答えは $0$ 。
$dp_i$ を「最後に $Y$ に振り分けた数の番号が $i$ であるときの振り分け方の総数」とし， $dp_0=1$ とする。また， $id$ を「現時点で遷移してくることが可能な番号の最小値」とし， $id=0$ とする。 $i$ が小さい順にこれを埋める。最初に， $dp_i += dp_{i-1}$ とする。 $S_i-S_j\geq B$ をみたす最大の $j$ を $s$ とし， $s\geq id$ であれば $dp_i += dp_s-dp_{id-1}$ とする( $s\lt id$ のときは遷移できない)。最後に， $S_i-S_{i-1}\lt A$ であれば $id=i-1$ とする。
答えは， $dp_N-dp_{id-1}$ である。