けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

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 マス目は被覆していてもいい)。

f:id:drken1215:20190220214243p:plain

さて、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;
}

解法 3: 包除原理

正真正銘の包除原理による解法もあるっぽい。

 N マスの任意の部分集合  S に対して、 S を被覆しない場合の数を  f(S) とすると ( S 以外を被覆するかどうかは問わない)

  •  \sum_{S} (-1)^{|S|} f(S)

で求められることがわかる。 S がサイズ  2^{N} になるため、問題に応じて上手く求めることになる。

  •  S のサイズ  k を固定すると  f(S) の値が一定だったりする
  • DP によってサイズ  k の値でまとめたときの  f(S) の総和が求められたりする

といった構造を利用することがほとんどになる。今回は 2 番目の方法で明快に解くことができる。その方法については olphe さんの

に詳細がある。