ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AGC009 C - Division into Two

問題
提出コード

解法

集合X,Yを、集合0、集合1とし、A,BL_{0},L_{1}とします。

  • dp[i][j] = i番目の要素まで見て、i番目の要素を集合jに入れるような振り分け方のパターン数

を数えます。
[l,i]という区間が集合jに入り、その前後はもう片方の集合に振り分けられるパターンを考えます。このような操作ができる条件は、

  • S_{i+1} - S_{l-1} \geq L_{1-j}

  • S_{k+1}-S_{k} \geq L_{j} (l \leq k \lt i)

の二つを満たすことです。
逆に、これらの条件を満たすlについて、[l,i]を集合jに入れる、という操作ができるので、
dp[i][j] = \sum_{l} dp[l-1][1-j]
という遷移が考えられます。
1つめの条件は、それぞれのiについて二分探索を用いて計算ができます。
S_{i + 1} - L_{1-j} \lt S_{k}となるようなkを二分探索で求めます。すると、 lとして選べるのはk-1以下です。

2つめの条件は前計算ができます。
S_{m + 1} - S_{m} \lt L_{j}となるようなm区間を区切っていきます。 i番目の要素についてみると、lとして選べるのは、その要素が所属している区間の要素のみになります。

以上で、ある要素iについて選べるl区間が求まったので、その区間の総和を求めてあげればDPの遷移が行えます。
区間和による遷移なので、累積和やセグ木で簡単に高速化ができます。
答えはdp[N][0] + dp[N][1]です。