AGC009 C - Division into Two
解法
集合を、集合0、集合1とし、をとします。
- 番目の要素まで見て、番目の要素を集合に入れるような振り分け方のパターン数
を数えます。
という区間が集合に入り、その前後はもう片方の集合に振り分けられるパターンを考えます。このような操作ができる条件は、
の二つを満たすことです。
逆に、これらの条件を満たすについて、を集合に入れる、という操作ができるので、
という遷移が考えられます。
1つめの条件は、それぞれのについて二分探索を用いて計算ができます。
となるようなを二分探索で求めます。すると、 として選べるのは以下です。
2つめの条件は前計算ができます。
となるようなで区間を区切っていきます。
番目の要素についてみると、として選べるのは、その要素が所属している区間の要素のみになります。
以上で、ある要素について選べるの区間が求まったので、その区間の総和を求めてあげればDPの遷移が行えます。
区間和による遷移なので、累積和やセグ木で簡単に高速化ができます。
答えはです。