AGC009 C - Division into Two
袋X, Yがあり、S[i]の数字が書かれたN個のボールが与えられる。それぞれの袋の中ではボールの数字の差がそれぞれA以上、B以上になっているように振り分けたい。そのような振り分け方は何通りあるか？
A < Bとなるように必要があればswapしておく。
dp1[i]をi番目のボールをXに格納する組み合わせ、dp2[i]をi番目のボールをYに格納する組み合わせとする。
まずYの方について、自由にボールを入れるとする。つまりdp2の更新だが、単純に既に既に入っているボールの最大値を見る。
dp[i + 1] = Σdp2[k] (kはS[k] + B <= S[i + 1]の範囲) となるが、これは尺取＋累積和を使うことでO(1)で計算可能。
次にdp1はdp2という制約の元(既に幾つかのボールがYに入っているという制約)、S[i+1]-S[i]がA未満かそうでないかで漸化式が異なる。A未満ならば一つ前は必ずYに格納されており、その次にXに格納される。ただし、S[i+2] - S[i] < Aというボールがあった場合は事前に0を出力しておく。そうでない場合はdp1[i + 1] = dp2[i] となる。
A以上の場合、一つ前のぼーるがXだろうとYだろうとどっちでも良いのでdp1[i + 1] = dp1[i] + dp2[i]である。
全体でO(N)。
いろんな漸化式が組めるが高速化すると上のように落ち着くらしい。
