C++の練習を兼ねて, AtCoder Regular Contest 010 の 問題A (A – 名刺交換) ~ 問題B (B – 超大型連休) を解いてみた.
■感想.
1. 問題A は, 名刺の残数が, 0 になる日が, 途中で, 何回有っても OK である点が面白いと感じた.
2. 問題B は, 12月31日時点で, 大型連休が継続中であるかを考える必要がある点が面白いと感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
■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 main(){ // 1. 入力情報. int N, M, A, B; scanf("%d %d %d %d", &N, &M, &A, &B); // 2. 名刺が足りなくなる場合があるか? int ans = 0, c; rep(i, M){ scanf("%d", &c); if(N <= A) N += B; N -= c; if(N < 0){ ans = i + 1; break; } } // 3. 出力. if(ans) printf("%d\n", ans); else puts("complete"); 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 |
[入力例] 100 3 0 100 10 20 30 [出力例] complete ※AtCoderのテストケースより [入力例] 100 4 0 100 10 20 30 40 [出力例] complete ※AtCoderのテストケースより [入力例] 100 4 0 100 50 40 30 20 [出力例] 3 ※AtCoderのテストケースより [入力例] 100 4 10 100 50 40 30 20 [出力例] complete ※AtCoderのテストケースより [入力例] 5 3 20 10 15 5 20 [出力例] 3 ※AtCoderのテストケースより [入力例] 12 7 30 23 15 5 38 17 30 7 22 [出力例] 5 [入力例] 12 7 30 23 15 5 38 17 29 7 39 [出力例] complete |
■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 |
#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 days[999]; int past[] = {0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335}; // m/d の 情報を, 経過日数に変換. // @param md: 月, 日. // @return: 経過日数. int toDay(string md){ // '/' で 分割. int pos = md.find("/"); string sm = md.substr(0, pos); string sd = md.substr(pos + 1); // 前月分までの経過日数. int im = stoi(sm), id = stoi(sd); int m = past[im - 1]; // 今月分の経過日数を加算. int ret = m + id; // 返却. return ret; } int main(){ // 1. 入力情報. int N; scanf("%d", &N); // 2. 土日を確定. repx(i, 1, 367){ if(i % 7 == 0) days[i]++; // 土曜日. if(i % 7 == 1) days[i]++; // 日曜日. } // 3. 祝日 or 振替休日. rep(i, N){ char c[111]; scanf("%s", c); string sh(c); int ih = toDay(sh); // 祝日. // 祝日が土日ならば, 平日に移動. while(days[ih]) ih++; days[ih]++; } // 4. 連休の最大値. int ans = 0, s = 0, e = 0; repx(i, 1, 367){ if(days[i]){ if(s == 0) s = i, e = s + 1; else e++; }else{ ans = max(ans, e - s); s = 0, e = 0; } } ans = max(ans, e - s); // 12/31 時点で, 大型連休が継続中だった場合. // 5. 出力. 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 |
[入力例] 1 1/9 [出力例] 3 ※AtCoderのテストケースより [入力例] 1 1/10 [出力例] 2 ※AtCoderのテストケースより [入力例] 1 1/7 [出力例] 3 ※AtCoderのテストケースより [入力例] 2 1/7 1/9 [出力例] 4 ※AtCoderのテストケースより [入力例] 12 4/30 5/1 5/2 5/3 5/4 7/14 7/20 7/16 7/15 7/18 7/23 12/24 [出力例] 10 [入力例] 12 12/31 12/30 12/25 12/26 12/23 12/24 12/28 12/29 12/20 12/19 12/27 12/21 [出力例] 13 |
■参照サイト
AtCoder Regular Contest 010