はまやんはまやんはまやん

hamayanhamayan's blog

Count Arrays [CSAcademy #65 D]

https://csacademy.com/contest/round-65/task/count-arrays/

Q個の区間がある。
i番目の区間は[L[i],R[i]]の区間に少なくとも1つは0が含まれるという条件。
全ての区間の条件をみたす長さNのバイナリ列は何通りあるか。
※バイナリ列 : 0と1からなる文字列

前提知識

解法

区間について、これをみたす数え上げ」という段階でインラインDP感、区間の右端について左端を隣接リストのように保持して処理していくんじゃないかなという感覚がある。
と言われてもピンと来ないだろうので、まずは計算量を越えるDPを考えよう。
 
区間についてはまずは無視して考える。
「dp[i][j] := i番目の文字列まで確定していて、最後に0があるのがj番目」
これを更新していくことを考えよう。
遷移を考えると、0を最後に置く、1を最後に置くの2通りがあるので、基本はこれをやればいい。
dp[i + 1][j] += dp[i][j] // 1を最後に置く
dp[i + 1][i + 1] += dp[i][j] // 0を最後に置く
これをより、更新しやすくするために、このように変えてみよう。
dp[i + 1][j] = dp[i][j] (j < i + 1)
dp[i + 1][i + 1] = sum{j = 0..i} dp[i][j]
こうすると、インラインDPで扱えるDPとなる。
 
これで区間を考える。
[L, R]の区間について考えると、dp[R][0]~dp[R][L-1]は条件を満たさない組み合わせ数となってしまう。
これはR番目まで確定しているのに最後に0が出て来るのがL-1以下なので[L,R]に0が1つもない状態になるためである。
なので、R番目まで確定させた段階でL未満のdp値は無視して考える。つまり0として考える必要がある。
これは遅延評価セグメントツリーで[0,L-1]を0としてしまってもいいが、関係してくるのはdp[i+1][i+1]の更新だけなので、
0となっている座標を保存しながらやっていっても良い。
下の実装では変数lを有効な左端として保持しながらdpのgetを行っている。
このために区間の右端について左端を保持しておいて、有効な左端を更新しながらやるとAC
 
※ dpをsegtreeでやっているがbitでやるべき

SegTree<int, 1 << 17> dp; // get: 区間総和, update: 代入
int N, Q;
vector<int> E[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, Q) {
        int L, R; cin >> L >> R;
        E[R].push_back(L);
    }

    dp.update(0, 1);
    int l = 0;
    rep(i, 0, N + 1) {
        fore(j, E[i]) l = j;
        // 0を置く
        dp.update(i + 1, dp.get(l, i + 1));
    }

    int ans = dp.get(l, N + 1);
    cout << ans << endl;
}