2019-02-20

全国統一プログラミング王決定戦本選 E - Erasure (700 点)

AtCoder AtCoder700点 unrated公式コン数え上げ問題 DP 包除原理ナップサックDP 二項係数区間操作操作:区間被覆する方法の数え上げダブルカウントを防ぐ場合分け操作:上書き補集合を考える被覆区間の連結関係に関する問題解空間:O(2^N)通りの選択肢

700 点は絶対落とさないようにしたい！！！

本番、DP と包除原理の二通りの方針が早期に見えて、「どちらかで詰まったらどちらかに立ち戻ろう」と思いながら DP に突き進んで見た。それでちゃんと通ってよかった。

問題へのリンク

問題概要

長さ $N$ の区間がある。
これに対して、長さが $K+1$ 以上の部分区間が $(N−K)×(N−K+1)/2$ 個考えられる。

これらの部分区間から何個か選ぶ方法のうち、選んだ区間が元の区間全体を被覆するものが何通りあるか、1000000007 で割ったあまりで求めよ。

制約

$1 \le K+1 \le N \le 5000$

考えたこと

お！！！ $O(N^{2})$ が間に合うっぽい！！！なので計算量的には $O(NK)$ が間に合うことになる。

さて、ふと思ったのが

区間を選んでいく系は DP (特に高速化が要求されることが多い)
余事象をとると考えやすいかも。各マスの組合せについて、それらを被覆しない場合の数は数え上げやすい。ゆえに包除原理がやりやすそう。

というわけで、考察初期段階で DP と包除原理の二通りの方針が浮かんだ中、本番は DP で解き切れた。包除原理も復習しておきたい。

解法 1: DP

こういう区間系の問題、DP だとわかっても詰めるのに時間がかかるのがよくない。。。

区間の終端を見るのがよいことが多い気がする
特に区間の被覆について扱う問題については、「初めて覆われなくなった部分」に着目するとよい

ということが多い気がする。この辺の思考はもうテンプレ化してしまいたい。さて、DP を

dp[ i ][ j ] := 最初の i マス分に含まれる区間のみを用いて、最初の j マス分を被覆して j +1 マス目は被覆しないような場合の数

とする。特に dp[ i ][ i ] は最初の i マスすべてをきっちり被覆する場合を表す。注意点として、例えば dp[ 10 ][ 4 ] は以下のような場合も含む (5 マス目は被覆してはいけないが、6 マス目は被覆していてもいい)。

さて、dp[ i ][ j ] から dp[ i + 1 ][ j ] への遷移を考える。すなわち、終端を i + 1 であるような長さ K + 1 以上の区間は $\max(0, i + 1 - K)$ 個あるが、そのそれぞれについて「使う」「使わない」の選択が $2^{\max(0, i + 1 - K)}$ 通りあって、それぞれが DP 遷移にどのような影響を及ぼすのかを場合分けして考える。

j の値が変わらないとき

j + 1 マス目以降はいくら被覆してもいいが、j マス目を覆ってはいけない。したがって後ろの (i + 1) - (j + 1) = i - j マス内に含まれる

max(0, i - j - K) 個

の区間について、「使う」「使わない」を自由に選択してよい。よって遷移は

dp[ i + 1 ][ j ] += dp[ i ][ j ] × $2^{\max(0, i - j - K)}$

となる。

j の値が変わるとき

今考えている区間はすべて終端が i + 1 なので、j の値が変わるなら j = i + 1 になる。条件は「j + 1 から i + 1 までをすべて覆うこと」である。それを満たす個数は、全体から「j の値が変わらないとき」を引けば求められるので

dp[ i + 1 ][ i + 1 ] += dp[ i ][ j ] × ( $2^{\max(0, i + 1 - K)} - 2^{\max(0, i - j - K)}$ )

となることがわかる。

#include <iostream>
using namespace std;

const int MAX = 5100;
const int MOD = 1000000007;

long long N, K;
long long dp[MAX][MAX];
long long p[MAX];

int main() {
    cin >> N >> K;
    p[0] = 1;
    for (int i = 1; i < MAX; ++i) p[i] = p[i-1] * 2 % MOD;
    dp[0][0] = 1;
    for (long long i = 0; i <= N; ++i) {
        for (long long j = 0; j <= i; ++j) {
            long long num = max(0LL, i-j-K);
            (dp[i+1][j] += dp[i][j] * p[num] % MOD) %= MOD;          
            if (i >= K) {
                long long num1 = i-K+1, num2 = max(0LL, i-j-K);
                (dp[i+1][i+1] += dp[i][j] * (p[num1] - p[num2] + MOD) % MOD) %= MOD;
            }
        }
    }
    cout << dp[N][N] << endl;
}

解法 2: 除原理

この方法は包除原理というよりは除原理かもしれない。

dp[ i ] := 最初の i マスについての、被覆できる場合の数

として、この余事象を求めることを考える。余事象において、被覆されていないマスのうち最左がどこかで場合分けする。

被覆されてない最左のマスが j 番目であるような場合の数は、dp[ j ] × pat[ i - (j + 1) ]

という風になる。ここで pat[ a ] は、a マス分について大きさ K + 1 以上の区間それぞれについて「選ぶ」「選ばない」を決める方法の数を表していて、

pat[ a ] = $2^{C(\max(0, a - K), 2)}$

となる。整理すると、

dp[ i ] = pat[ i ] - $\sum_{j = 0}^{i - 1}$ (dp[ j ] × pat[ i - j - 1 ])

となる。これを i = 1, 2, 3, ..., N と順に更新して行けばよい。

#include <iostream>
using namespace std;

const int MAX = 5100;
const int MOD = 1000000007;

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long N, K;
long long dp[MAX];
long long pat[MAX];

int main() {
    cin >> N >> K;
    for (long long a = 0; a <= N; ++a) {
        long long b = max(0LL, a - K);
        pat[a] = modpow(2LL, b * (b + 1) / 2, MOD);
    }
    dp[0] = 1;
    for (int i = 1; i <= N; ++i) {
        dp[i] = pat[i];
        for (int j = 0; j < i; ++j) {
            dp[i] -= dp[j] * pat[i-j-1] % MOD;
            dp[i] = (dp[i] % MOD + MOD) % MOD;
        }
    }
    cout << dp[N] << endl;
}