C++の練習を兼ねて, AtCoder Regular Contest 045 の 問題A (スペース高橋君) ～ 問題B (ドキドキデート大作戦高橋君) を解いてみた.
■感想.
1. 久しぶりに, 解説確認前に, AC版に到達できたので, 良かったと思う..
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 045 解説 を ご覧下さい.
■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 38 39 40 41 42 43 44 |
// C++(GCC 9.2.1) #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 pb push_back int main(){ // 1. 入力情報. char c[1010]; scanf("%[a-zA-Z@ ]", c); string S(c); // printf("%s\n", S.c_str()); // 2. スペースで分割. int l = S.size(); vector<string> T; string s; rep(i, l){ if(S[i] == ' '){ T.pb(s); s = ""; }else{ s.pb(S[i]); } } if(s.size() > 0) T.pb(s); // 3. 出力. int tl = T.size(); rep(i, tl){ if(T[i] == "Left") printf("<"); if(T[i] == "Right") printf(">"); if(T[i] == "AtCoder") printf("A"); if(i < tl - 1) printf(" "); } puts(""); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
[入力例] Left Right AtCoder [出力例] < > A ※AtCoderのテストケースより [入力例] Left Left Right Right AtCoder [出力例] < < > > A ※AtCoderのテストケースより [入力例] Right Right AtCoder Left Left AtCoder [出力例] > > A < < A ※AtCoderのテストケースより |
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; using vp = vector<P>; using vi = vector<int>; #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 #define a first #define b second int a[303030], b[303030]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); vp v; rep(i, M){ int s, t; scanf("%d %d", &s, &t); s--; a[s]++; a[t]--; v.pb({s, t}); } // 2. いもす法. rep(i, N + 1) a[i + 1] += a[i]; // 3. 掃除区間を整理(累積和). rep(i, N + 1) if(a[i] >= 2) b[i + 1] = 1; // 指定された教室が, 2個以上の区間に含まれる. rep(i, N + 1) b[i + 1] += b[i]; // 4. サボってもバレない掃除区間を抽出. vi ans; rep(i, M){ int d = v[i].b - v[i].a; if(b[v[i].b] - b[v[i].a] == d) ans.pb(i + 1); } // 5. 出力. printf("%d\n", ans.size()); for(auto &p : ans) printf("%d\n", p); 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 |
[入力例] 10 5 1 4 5 5 6 8 9 10 5 6 [出力例] 2 2 5 ※AtCoderのテストケースより [入力例] 3 6 1 1 1 1 2 2 2 2 3 3 3 3 [出力例] 6 1 2 3 4 5 6 ※AtCoderのテストケースより [入力例] 10 3 1 4 2 6 6 10 [出力例] 0 ※AtCoderのテストケースより [入力例] 30 11 1 5 5 10 10 13 13 15 15 18 18 23 23 25 25 27 28 30 11 19 7 8 [出力例] 5 3 4 5 10 11 |
■参照サイト
AtCoder Regular Contest 045