C++の練習を兼ねて, AtCoder Regular Contest 116 の 問題A (Odd vs Even) ~ 問題B (Products of Min-Max) を解いてみた.
■感想.
1. 規則性を抽出できたので, AC版まで到達できたと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 116 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題A/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 |
// 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--) int main(){ // 1. 入力情報. int T; scanf("%d", &T); rep(i, T){ // 与えられた整数. LL N; scanf("%lld", &N); // 倍数をチェック. int f = 0; if(N % 2 == 0) f++; if(N % 4 == 0) f++; // 出力. if(f == 0) puts("Odd"); if(f == 1) puts("Same"); if(f == 2) puts("Even"); } 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 2 998244353 1000000000000000000 [出力例] Same Odd Even ※AtCoderのテストケースより [入力例] 17 222079 533860 941892 685490 243916 404856 695734 34365 572866 940162 470243 133907 930142 667476 669648 477556 294291 [出力例] Odd Even Even Same Even Even Same Odd Same Same Odd Odd Same Even Even Even Odd |
■C++版プログラム(問題B/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 |
// 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], sum[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld", &a[i]); // 2. sort. sort(a, a + N); // 3. max(B) の 和 は? // ex. // a = {a1, a2, a3, a4, a5} の 場合. // min(B) max(B) の 和. // a1 sum[1] = a1 * 1 + a2 * 1 + a3 * 2 + a4 * 4 + a5 * 8 (16通り) // a2 sum[2] = a2 * 1 + a3 * 1 + a4 * 2 + a5 * 4 (8通り) // a3 sum[3] = a3 * 1 + a4 * 1 + a5 * 2 (4通り) // a4 sum[4] = a4 * 1 + a5 * 1 (2通り) // a5 sum[5] = a5 * 1 (1通り) // -> 上記から, a1 * sum[1] * ... * a5 * sum[5] (31通りの和) を 計算すれば良さそうに見える. sum[N - 1] = a[N - 1]; repr(i, N - 2, 0){ sum[i] = sum[i + 1] * 2LL; sum[i] += (MOD - a[i + 1]); sum[i] += a[i]; sum[i] %= MOD; } // 4. 集計. LL ans = 0; rep(i, N) ans += (a[i] * sum[i]), 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 |
[入力例] 3 2 4 3 [出力例] 63 ※AtCoderのテストケースより [入力例] 1 10 [出力例] 100 ※AtCoderのテストケースより [入力例] 7 853983 14095 543053 143209 4324 524361 45154 [出力例] 206521341 ※AtCoderのテストケースより [入力例] 12 31 41 59 26 53 58 97 93 23 84 62 64 [出力例] 10307796 |
■参照サイト
AtCoder Regular Contest 116