C++の練習を兼ねて, AtCoder Regular Contest 024 の 問題A (A – くつがくっつく) ～ 問題B (B – 赤と黒の木) を解いてみた.
■感想.
1. 問題Bは, もっとも長く連続する 0 もしくは 1 の パターンに対して, 計算で求まることに気付いたので, AC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトARC 024 解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; #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 l[111], r[111]; // 左足, 右足の靴のサイズ. int main(){ // 1. 入力情報. int L, R, x; scanf("%d %d", &L, &R); rep(i, L){ scanf("%d", &x); l[x]++; } rep(i, R){ scanf("%d", &x); r[x]++; } // 2. 作成可能な靴のペア数の最大値を集計. int ans = 0; rep(i, 111) ans += min(l[i], r[i]); // 3. 出力. printf("%d\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 |
[入力例] 3 3 20 21 22 30 22 15 [出力例] 1 ※AtCoderのテストケースより [入力例] 3 4 10 11 10 12 10 11 25 [出力例] 2 ※AtCoderのテストケースより [入力例] 5 5 10 10 10 10 10 10 10 10 10 10 [出力例] 5 ※AtCoderのテストケースより [入力例] 5 5 10 11 12 13 14 30 31 32 33 34 [出力例] 0 ※AtCoderのテストケースより [入力例] 45 75 33 22 12 34 13 36 36 18 14 10 17 10 38 13 27 21 14 11 18 29 31 28 30 33 19 29 12 24 35 17 37 30 29 31 17 27 29 10 26 11 37 36 19 18 36 14 25 18 33 31 28 13 31 25 35 30 37 18 10 22 12 37 36 35 27 21 15 17 35 35 20 18 37 37 27 15 21 33 31 35 18 23 36 38 36 25 19 19 19 14 30 27 11 28 11 32 22 10 12 14 19 17 36 10 12 11 14 36 35 12 36 14 37 38 35 31 14 12 23 12 [出力例] 36 |
■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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
#include <bits/stdc++.h> using namespace std; #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 a first #define b second int br[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d", &br[i]); // 2. 0, 1 の 切り替わり箇所は？ int cur = -1, bef = br[0], s = -1; repx(i, 1, N){ // 今回分更新. cur = br[i]; // 前回と異なる場合は, 出現位置を保存して終了. if(bef != cur){ s = i; break; } // 前回分更新. bef = cur; } // 3. 全部同じ色の場合は, -1 を 出力. if(s == -1){ puts("-1"); return 0; } // 4. 0 ～ (s - 1)番目 までを, br の 後ろにくっつける. // ex. // 110111 -> 11011111 rep(i, s) br[i + N] = br[i]; // 5. 0, 1 の 連続する長さを測定. map<int, int> mb, mr; bef = br[s]; int c = 0, maxC = 0; repx(i, s, N + s){ // 今回分更新. cur = br[i]; // 前回と同じ場合は, カウンターを増やす. if(bef == cur){ c++; }else{ // 黒色. if(bef == 0) mb[c]++; // 赤色. if(bef == 1) mr[c]++; // 最大値更新. maxC = max(maxC, c); // カウンターを初期化. c = 1; } // 前回分更新. bef = cur; } // 黒色. if(bef == 0) mb[c]++; // 赤色. if(bef == 1) mr[c]++; // 最大値更新. maxC = max(maxC, c); // puts("--- black ---"); // for(auto i = mb.begin(); i != mb.end(); ++i) printf("key=%d value=%d\n", i->a, i->b); // puts("--- red ---"); // for(auto i = mr.begin(); i != mr.end(); ++i) printf("key=%d value=%d\n", i->a, i->b); // 6. すべての木の色が変わらなくなる日が何日目か？ int ans = (maxC + 1) / 2; // 7. 出力. printf("%d\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 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 |
[入力例] 5 0 1 1 1 0 [出力例] 2 ※AtCoderのテストケースより [入力例] 6 1 1 0 1 1 1 [出力例] 3 ※AtCoderのテストケースより [入力例] 3 1 1 1 [出力例] -1 ※AtCoderのテストケースより [入力例] 100 0 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0 0 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 1 0 0 0 1 [出力例] 5 |
■参照サイト
AtCoder Regular Contest 024