C++の練習を兼ねて, AtCoder Beginner Contest 230 の 問題F (Predilection) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説内容を実装する形で, AC版に到達できたと思う.
2. 実装に苦労したものの, 個人的には, 数列の性質を, 動的計画法に持ち込むことで, 操作後の数列の種類数がカウントできるロジックが, 面白いと感じた.
3. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 230 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F/AC版).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
// 説き直し. // https://atcoder.jp/contests/abc230/editorial/91 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) const LL MOD = 998244353; LL a[202020], aCum[202020], dp[202020], dpCum[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld", &a[i]); // 2. 累積和. // -> aCum[i + 1] = a[i] + a[i - 1] + ... + a[0] rep(i, N) aCum[i + 1] = aCum[i] + a[i]; // 3. dp更新. map<LL, int> m; // {累積和, 最大index} m[0] = 0; dp[0] = 1; dpCum[0] = 0; repx(i, 1, N + 1){ // 3-1. a[j] + a[j + 1] + ... + a[i] = 0 となる j があるか? int j = 0; if(m.count(aCum[i])) j = m[aCum[i]]; // 前回以前に, aCum[i + 1] が 出現している場合. // 3-2. 最大index を 更新. m[aCum[i]] = i; // 3-3. dpCum更新(dpCum[i] = dp[i - 1] + dp[i - 1] + ... + dp[0]). dpCum[i] = dpCum[i - 1] + dp[i - 1]; dpCum[i] %= MOD; // 3-4. dp更新(dp[i] = dp[i - 1] + dp[i - 2] + ... + dp[j] = dpCum[i] - dpCum[j] と 見る). dp[i] = dpCum[i] + MOD - dpCum[j]; dp[i] %= MOD; } // 4. 集計(aCum[N] - aCum[k] = 0 となる dp[k]). LL ans = 0; repx(k, 1, N + 1) if(aCum[N] == aCum[k]) ans += dp[k], ans %= MOD; // 5. 出力. printf("%lld\n", ans); return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
[入力例] 3 1 -1 1 [出力例] 4 ※AtCoderテストケースより [入力例] 10 377914575 -275478149 0 -444175904 719654053 -254224494 -123690081 377914575 -254224494 -21253655 [出力例] 321 ※AtCoderテストケースより [入力例] 5 3 -2 -1 5 -5 [出力例] 16 [入力例] 11 1 2 -3 -4 5 -6 5 4 -3 -2 1 [出力例] 928 [入力例] 15 -1 12 -3 9 -12 -3 0 -7 7 -1 5 17 -10 0 11 [出力例] 7680 [入力例] 33 3 1 -4 1 -5 9 -2 -6 5 3 -5 8 -9 7 -9 3 2 -3 8 -4 6 -2 -6 4 3 -3 -8 3 2 7 -9 5 0 [出力例] 19569121 [入力例] 50 3358 2443 9460 4339 -610 -3793 -15197 -10441 -5374 5738 10077 -9794 4846 8599 -3651 -367 2251 -5020 3168 3918 -625 3835 -2395 -9713 8180 8077 -1650 60 -4954 -8226 5051 9719 6910 -14987 563 5057 -7262 7238 393 -7147 -484 721 -2818 5914 -2261 -835 1032 1582 -1779 -1556 [出力例] 804371196 |
■参照サイト
AtCoder Beginner Contest 230