競プロやります。

競プロを頑張るブログです。

トップ > ABC/ARC > AtCoder Beginner Contest 130

AtCoder Beginner Contest 130

ABC/ARC

D - Enough Array

https://atcoder.jp/contests/abc130/tasks/abc130_d

方針

しゃくとり法が不慣れでかなり苦戦してしまいました。

連続部分列の左端の index を l で固定した時に、 \sum_{i=l}^{r} a_i \geq K となる右端 r は何通りあるかを考えます。

まず、部分列の左端を l として和を取ったとき、 r(l) で初めて和が K 以上になるとします。つまり、 \sum_{i=l}^{r-1} a_i < K \leq \sum_{i=l}^{r} a_i となるような r を r(l) とします。
制約より A の要素は全て正ですから、部分列の右端を r(l) より大きくしても、やはり和は K 以上のままです。よって、 l が左端のときの部分列の取り方は N - r(l) + 1 通りとなります。ここで、 A の最後に非常に大きな値 inf を追加しておくと、必ず r = N+1 で和が K を越えるので、部分列の取り方 N - r(l) + 1 が常に成立します。
以上より N - r(l) + 1 を、 l = 1,2,\dots , N について和を取れば答えが求まります。

r(l) を求めるのにはしゃくとり法を用いました。しゃくとり法については けんちょんさんの記事 が参考になります。

ソースコード

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    int N; ll K;  cin >> N >> K;
    vector<ll> a(N+2,0);
    for(int i=1; i<=N; i++) cin >> a[i];
    a[N+1] = 1e18; // A の末尾に inf を追加しておく

    ll ans = 0;
    ll sum = 0;
    int right = 1;
    for(int left = 1; left <= N; left++){
        // sum < K となる間、右端を広げながら sum に a[right] を加えていく
        // ここで a[N+1] = inf のため、必ず sum + a[N+1] >= K となる。
        // この while文を抜けた時の right が r(left) となる。
        while(sum + a[right] < K){
            sum += a[right];
            right++;
        }
        ans += N - right + 1;
        sum -= a[left];
    }
    cout << ans << endl;
}

E - Common Subsequence

https://atcoder.jp/contests/abc130/tasks/abc130_e

方針

\text{dp}(n, m) = ( 末尾が S_n, T_m であるような共通部分列の数 ) 、とします。ただし、 n=0 のときは S からは何も取らなかった場合とし、 m = 0 のときは T からは何も取らなかった場合であると考えます。求める答えは
　 \displaystyle \sum_{n=0}^{N} \sum_{m=0}^{M} \text{dp}(n,m)
となります。

まず、元の数列から何も取らなかった空の数列は S, T 両方に共通の部分列になりますから、 \text{dp}(0,0) = 1 です。また、当然 S_n = T_m でなければいけないので、 S_n \neq T_m のとき \text{dp}(n, m) = 0 です。
S_n = T_m のとき、末尾が S_n ( = T_m) であるような部分列は、 \{ S_1, \dots , S_{n-1} \} と \{ T_1, \dots , T_{m-1} \} の共通部分列 (空の数列を含む) の末尾に S_n を付け加えたものになるので、
　　 \displaystyle \text{dp}(n,m) = \sum_{i=0}^{n-1} \sum_{j=0}^{m-1} \text{dp}(i,j)
となります。
このシグマの計算を愚直に行うと、全ての \text{dp}(n,m) を求めるのに O(N^2 M^2) の計算が必要になってしまうので、上手く計算量を落とすことを考えます。


よく見ると S_n = T_m のときの \text{dp}(n,m) は、dpテーブルの2次元累積和の形で表せていることが分かります。そこで、
　 \displaystyle D(n, m) = \sum_{i=0}^{n} \sum_{j=0}^{m} \text{dp}(i,j)
とします。

これを用いると、 S_n = T_m のとき \text{dp}(n,m) = D(n-1,m-1) となります。
\text{dp}(n,m) が求まると、 D(n,m) = D(n,m-1) + D(n-1,m) + \text{dp}(n,m) - D(n-1,m-1) と更新できます。
そしてこの D(n,m) を用いると、次の \text{dp}(n+1, m+1) の計算を行えるようになるので、遷移を O(1) で行うことが出来ました。よってdpテーブル全体を O(NM) で求めることが出来ます。

なお最後の答えは、
　 \displaystyle \sum_{n=0}^{N} \sum_{m=0}^{M} \text{dp}(n,m) = D(N,M)
と表すことが出来ます。

ソースコード

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    int N, M;  cin >> N >> M;
    ll mod = 1e9+7;

    vector<ll> S(N+1,0), T(M+1,0);
    for(int i=1; i<=N; i++) cin >> S[i];
    for(int i=1; i<=M; i++) cin >> T[i];

    vector<vector<ll>> dp(N+1, vector<ll>(M+1,0));
    vector<vector<ll>> D(N+1, vector<ll>(M+1,0));
    // 空の数列は S, T 両方の共通部分列となるので dp[0][0] = 1
    // なおdp[0][1,2,……,M] = dp[1,2,……,N][0] = 0
    dp[0][0] = 1;

    // 以下2行は、上で初期化した dp と D の定義より従う
    for(int n=0; n<=N; n++) D[n][0] = 1;
    for(int m=0; m<=M; m++) D[0][m] = 1;


    for(int n=1; n<=N; n++) for(int m=1; m<=M; m++){
        // dp テーブルを更新する
        if(S[n] != T[m]){
            dp[n][m] = 0;
        }else{
            dp[n][m] = D[n-1][m-1];
        }

        // dp テーブルを更新したので、その累積和である D を更新する。
        // D[n][m] = D[n][m-1] + D[n-1][m] + dp[n][m] - D[n-1][m-1] を計算する
        D[n][m] = D[n-1][m];
        D[n][m] = (D[n][m] + D[n][m-1])%mod;
        D[n][m] = (D[n][m] + dp[n][m])%mod;
        D[n][m] = (D[n][m] - D[n-1][m-1])%mod;
        while(D[n][m]<0){
            // 最後の引き算で D[n][m] が負になった場合は、0 以上になるまで mod を足す。
            D[n][m] += mod;
        }
    }

    // dp テーブルの累積和が求める答え。
    cout << D[N][M] << endl;
}