C++の練習を兼ねて, AtCoder Regular Contest 120 の 問題A (Max Add) ～ 問題B (Uniformly Distributed) を解いてみた.
■感想.
1. 規則性に気付けたので, AC版に到達出来たと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 120 解説 の 各リンク を ご覧下さい.
■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 |
// 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--) LL a[202020], aMax[202020], aCum[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld", &a[i]); // 2. i番目までの最大値を保存. rep(i, N) aMax[i + 1] = max(aMax[i], a[i]); // 3. 累積和. rep(i, N) aCum[i + 1] = aCum[i] + a[i]; rep(i, N) aCum[i + 1] += aCum[i]; // 4. 出力. repx(i, 1, N + 1) printf("%lld\n", aMax[i] * i + aCum[i]); 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 |
[入力例] 3 1 2 3 [出力例] 2 8 19 ※AtCoderのテストケースより [入力例] 10 7 6 1 4 5 11 7 11 8 3 [出力例] 14 34 55 80 110 175 227 290 361 435 |
■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 49 50 51 52 53 54 |
// 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; int board[1010][1010]; // マスの色(0: 色なし, 1: 赤, 2: 青). int cnt[1010][3]; // 出現回数(0: 色なし, 1: 赤, 2: 青). int main(){ // 1. 入力情報. int H, W; scanf("%d %d", &H, &W); rep(i, H){ char c[505]; scanf("%s", c); rep(j, W){ if(c[j] == 'R') board[i][j] = 1; if(c[j] == 'B') board[i][j] = 2; } } // 2. 右上から左下に向かって, マスの色を確認. rep(k, H + W - 1){ rep(i, H + W - 1){ int j = k - i; if(j >= 0) cnt[k][board[i][j]]++; else break; } } // rep(i, H + W - 1) printf("n=%d r=%d b=%d\n", cnt[i][0], cnt[i][1], cnt[i][2]); // 3. 色なしのみをカウント. // -> 赤, 青が混在している場合は, 着色不可能と判定. // -> 開始地点, 終了地点も, '.' となる場合があるので, 注意. LL ans = 1; int noColor = 0; rep(i, H + W - 1){ if(cnt[i][1] && cnt[i][2]) ans = 0; if(!cnt[i][1] && !cnt[i][2]) noColor++; } // 4. 塗り方の総数は？ rep(i, noColor) ans <<= 1, 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 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
[入力例] 2 2 B. .R [出力例] 2 ※AtCoderのテストケースより [入力例] 3 3 R.R BBR ... [出力例] 0 ※AtCoderのテストケースより [入力例] 2 2 BB BB [出力例] 1 ※AtCoderのテストケースより [入力例] 2 2 .. .. [出力例] 8 [入力例] 5 10 RR..B...RR R.......RB ..B...R.B. .......B.. B...R.B..B [出力例] 128 [入力例] 20 25 .R..B....R............... R........B..B............ ......R.................. .......B................. B........B..R............ .....B.........B..R...... ........................R ...B..................... ............B.........R.. .B..B.................... ...............R......... ..B......B..............B .......................B. .................R....... .............R........... ...............R....B.... ......................... ......................... ......................... ........................R [出力例] 75497471 |
■参照サイト
AtCoder Regular Contest 120