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; }