AtCoder Beginner Contest 130
D - Enough Array
https://atcoder.jp/contests/abc130/tasks/abc130_d
方針
しゃくとり法が不慣れでかなり苦戦してしまいました。
連続部分列の左端の index を で固定した時に、 となる右端 は何通りあるかを考えます。
まず、部分列の左端を として和を取ったとき、 で初めて和が 以上になるとします。つまり、 となるような を とします。
制約より の要素は全て正ですから、部分列の右端を より大きくしても、やはり和は 以上のままです。よって、 が左端のときの部分列の取り方は 通りとなります。ここで、 の最後に非常に大きな値 inf を追加しておくと、必ず で和が を越えるので、部分列の取り方 が常に成立します。
以上より を、 について和を取れば答えが求まります。
を求めるのにはしゃくとり法を用いました。しゃくとり法については けんちょんさんの記事 が参考になります。
ソースコード
#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
方針
末尾が であるような共通部分列の数、とします。ただし、 のときは からは何も取らなかった場合とし、 のときは からは何も取らなかった場合であると考えます。求める答えは
となります。
まず、元の数列から何も取らなかった空の数列は 両方に共通の部分列になりますから、 です。また、当然 でなければいけないので、 のとき です。
のとき、末尾が であるような部分列は、 と の共通部分列 (空の数列を含む) の末尾に を付け加えたものになるので、
となります。
このシグマの計算を愚直に行うと、全ての を求めるのに の計算が必要になってしまうので、上手く計算量を落とすことを考えます。
よく見ると のときの は、dpテーブルの2次元累積和の形で表せていることが分かります。そこで、
とします。
これを用いると、 のとき となります。
が求まると、 と更新できます。
そしてこの を用いると、次の の計算を行えるようになるので、遷移を で行うことが出来ました。よってdpテーブル全体を で求めることが出来ます。
なお最後の答えは、
と表すことが出来ます。
ソースコード
#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; }