C++の練習を兼ねて, AtCoder Regular Contest 130 の 問題A (Remove One Character) ~ 問題B (Colorful Lines) を解いてみた.
■感想.
1. 問題A, Bは, 方針を絞り込むことが出来たので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 130 解説 の 各リンク を ご覧下さい.
■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 33 34 35 36 37 |
// 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 N; char s[303030]; scanf("%d %s", &N, s); s[N] = '#'; // 番兵. // 2. 文字列の連続箇所を把握. LL ans = 0, t = 0; char bef = '.', cur; rep(i, N + 1){ // 今回分. cur = s[i]; // 集計. if(bef == cur) t++; else ans += t * (t - 1) / 2, t = 1; // 前回分. bef = cur; } // 3. 出力. 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 |
[入力例] 7 abbbcca [出力例] 4 ※AtCoderのテストケースより [入力例] 4 xxxx [出力例] 6 ※AtCoderのテストケースより [入力例] 2 pp [出力例] 1 ※AtCoderのテストケースより [入力例] 2 st [出力例] 0 ※AtCoderのテストケースより [入力例] 121 aaabccccdeeeeefffffffffgghhhhhhiiiiijjjkkkkkllllllllmmmmmmmmmnnnnnnnooooooooopppqqrrrssssssssttttuuuuuuvvwwwwwwxxxxyyyzzz [出力例] 299 [入力例] 351 abbcccddddeeeeeffffffggggggghhhhhhhhiiiiiiiiijjjjjjjjjjkkkkkkkkkkkllllllllllllmmmmmmmmmmmmmnnnnnnnnnnnnnnoooooooooooooooppppppppppppppppqqqqqqqqqqqqqqqqqrrrrrrrrrrrrrrrrrrsssssssssssssssssssttttttttttttttttttttuuuuuuuuuuuuuuuuuuuuuvvvvvvvvvvvvvvvvvvvvvvwwwwwwwwwwwwwwwwwwwwwwwxxxxxxxxxxxxxxxxxxxxxxxxyyyyyyyyyyyyyyyyyyyyyyyyyzzzzzzzzzzzzzzzzzzzzzzzzzz [出力例] 2925 [入力例] 1807 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeffffffffffffffffffffffgggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggghhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhiiiiiiiiiiiiiiijjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkllllllllllllllllllllllllllllmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnoooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrsssssssssssssssssssssssssssssssssstttttttttttttttttttttttttttttttttuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz [出力例] 78024 |
■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 55 56 57 58 59 60 61 |
// 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 ans[303030]; int t[303030], n[303030], c[303030]; int main(){ // 1. 入力情報. int H, W, C, Q; scanf("%d %d %d %d", &H, &W, &C, &Q); rep(i, Q) scanf("%d %d %d", &t[i], &n[i], &c[i]); // 2. マスの色は? int rCount = 0, cCount = 0; set<int> rSt, cSt; repr(i, Q - 1, 0){ // 2-1. 行方向. if(t[i] == 1){ // まだ出現してない場合. if(!rSt.count(n[i])){ // 行を保存. rSt.insert(n[i]); // 列数を考慮してカウント. ans[c[i]] += (LL)(W - cCount); // 行数カウント. rCount++; } } // 2-2. 列方向. if(t[i] == 2){ // まだ出現してない場合. if(!cSt.count(n[i])){ // 列を保存. cSt.insert(n[i]); // 行数を考慮してカウント. ans[c[i]] += (LL)(H - rCount); // 列数カウント. cCount++; } } } // 3. 出力. repx(i, 1, C + 1){ printf("%lld", ans[i]); printf("%s", (i < C) ? " " : "\n"); } 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 73 74 75 76 77 78 |
[入力例] 4 5 6 5 1 1 6 1 3 3 2 2 4 2 4 2 1 1 2 [出力例] 0 8 3 3 0 0 ※AtCoderのテストケースより [入力例] 1000000000 1000000000 3 5 1 1 2 1 2 2 1 3 2 1 4 2 1 5 2 [出力例] 0 5000000000 0 ※AtCoderのテストケースより [入力例] 10 12 7 15 1 7 2 2 12 5 2 8 2 2 6 2 2 9 2 1 5 5 1 7 5 2 4 3 2 10 2 2 8 5 1 5 6 2 2 1 2 8 6 2 6 3 2 6 1 [出力例] 20 17 9 0 15 19 0 [入力例] 20 21 11 28 1 13 8 2 11 11 1 5 10 1 11 2 2 7 8 2 19 4 1 1 7 1 10 2 1 20 1 2 17 1 2 5 1 1 13 11 1 4 2 1 11 8 2 9 3 1 7 3 2 7 5 2 21 5 1 19 9 2 3 6 2 10 1 2 17 9 1 20 7 2 7 10 1 1 8 2 7 11 2 21 8 1 19 11 [出力例] 30 29 32 12 0 17 19 53 17 13 66 |
■参照サイト
AtCoder Regular Contest 130