C++の練習を兼ねて, AtCoder Beginner Contest 353 の 問題C (Sigma Problem) ～ 問題D (Another Sigma Problem) を解いてみた.
■感想.
1. 問題C は, 方針が見えなかったため, 解説プログラムを参考に, AC版に到達できたと思う.
2. 個人的には, 尺取り法の復習ができたので, 非常に良かったと思う.
3. 引き続き, 時間があれば, 過去問を確認していきたいと思う.
本家のサイト AtCoder Beginner Contest 353 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C／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 |
// 解き直し. // https://atcoder.jp/contests/abc353/editorial/9957 // C++20(GCC 12.2) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; #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--) #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N; scanf("%d", &N); vl a(N); LL ans = 0; rep(i, N){ scanf("%lld", &a[i]); ans += a[i]; } ans *= (N - 1); // 2. sort. sort(all(a)); // 3. 尺取り法. int j = N; rep(i, N){ j = max(i + 1, j); while(j - 1 > i && a[j - 1] + a[i] >= 100000000) --j; ans -= (LL)(N - j) * 100000000; } // 4. 出力. 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 |
[入力例] 3 3 50000001 50000002 [出力例] 100000012 ※AtCoderテストケースより [入力例] 5 1 3 99999999 99999994 1000000 [出力例] 303999988 ※AtCoderテストケースより [入力例] 7 12345678 23456789 34567890 45678901 56789012 67890123 78901234 [出力例] 1017777762 |
■C++版プログラム(問題D／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 |
// C++20(GCC 12.2) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; #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--) #define pb push_back const LL MOD = 998244353; int main(){ // 1. 入力情報. int N; scanf("%d", &N); vl a(N); rep(i, N) scanf("%lld", &a[i]); // 2. 10 の 冪乗. vl cPow; cPow.pb(1LL); rep(i, 11) cPow.pb(cPow.back() * 10LL % MOD); // 3. 累積和. vl pCum(N + 1); rep(i, N) pCum[i + 1] = (pCum[i] + a[i]) % MOD; // 4. 集計(第二引数を基準に, 一括で足し込むようにする). // // ex. N = 5 // f(A1, A2) // f(A1, A3) + f(A2, A3) // f(A1, A4) + f(A2, A4) + f(A3, A4) // f(A1, A5) + f(A2, A5) + f(A3, A5) + f(A4, A5) LL ans = 0; repx(i, 1, N){ // 第二引数. ans += a[i] * i; ans %= MOD; // 第一引数. int d = to_string(a[i]).size(); ans += pCum[i] * cPow[d] % MOD; 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 |
[入力例] 3 3 14 15 [出力例] 2044 ※AtCoderテストケースより [入力例] 5 1001 5 1000000 1000000000 100000 [出力例] 625549048 ※AtCoderテストケースより [入力例] 7 5 7 12 17 1 20 3 [出力例] 9084 [入力例] 10 2024 5 11 2100 12345 54321 999999999 333 222 111 [出力例] 116320320 |
■参照サイト
AtCoder Beginner Contest 353