AtCoder Regular Contest 065 : F - シャッフル / Shuffling

問題概要

長さNの01文字列Sが与えられる。M個の数字ペア(Li, Ri)が与えられ、Sの区間[Li, Ri]の文字を自由に並び替える、という操作を順に行ったあとのSとしてありうるものが何通りあるか求めよ。ただしLiは必ず昇順になっているものとする。

N, M <= 3000

解法

dp(i, j): i文字目までで、0をj回使って作れる文字列の数

としてDPをする。このDPの遷移は、i文字目に0を使う/1を使う の2通りである。

ここでSのi文字目を見ているとき、iを区間に含むようなシャッフル操作LRがあれば、そのうち最大のRをr_maxと置く。なければr_max=iとする。このようにすると、「Sのi文字目までに使える0の数」は高々「Sのr_max文字目までに現れる0の数」と言うことができる。1の数も r_maxからこれを引けば出せる。

これを踏まえて dp(i, j) を更新することを考えると、上で出した「Sのi文字目までに使える0の数」がjより多ければ「使える0」が余るので dp(i+1, j+1) に遷移できる(ゼロを使うパターン)。同じように「Sのi文字目までに使える1の数」が i - j より多ければd(i+1, j) に遷移できる。

このDPは状態数 O(N2), 遷移 O(1) なので O(N2) でできる。

なおr_maxについてはシャッフル操作がLの昇順になっていることから尺取り法の要領でO(N+M)で逐次求めていくことができる。

感想

シャッフル操作の言い換えがキモという感じですが、dpの設計さえたどり着けなかったというのと、境界のあたりをうまいことやるのがめちゃくちゃつらかったです

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

immutable long MOD = 10^^9 + 7;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto S = readln.chomp;
    auto LR = M.iota.map!(_ => readln.split.map!(a => a.to!int - 1).array).array;

    auto zeros = new long[](N+1);
    foreach (i; 0..N) {
        zeros[i+1] = zeros[i] + (S[i] == '0');
    }

    auto dp = new long[][](N+1, N+1);
    dp[0][0] = 1;
    int rmax = 0;
    int q = 0;

    foreach (i; 0..N) {
        while (q < M && LR[q][0] <= i) {
            rmax = max(LR[q][1], rmax);
            q += 1;
        }
        rmax = max(rmax, i);
        long zero = zeros[rmax+1];
        long one = rmax + 1 - zero;

        foreach (j; 0..i+1) {
            long rest_zero = zero - j;
            long rest_one = one - (i - j);
            if (rest_zero < 0 || rest_one < 0) {
                continue;
            }
            if (rest_zero > 0) {
                dp[i+1][j+1] += dp[i][j];
                dp[i+1][j+1] %= MOD;
            }
            if (rest_one > 0) {
                dp[i+1][j] += dp[i][j];
                dp[i+1][j] %= MOD;
            }
        }
    }

    long ans = 0;
    foreach (a; dp[N]) {
        ans += a;
        ans %= MOD;
    }

    ans.writeln;
}