C++の練習を兼ねて, AtCoder Beginner Contest 001 の 問題D (D – 感雨時刻の整理) を解いてみた.
■感想.
1. 実装に苦労したものの, いもす法を使う方針で, AC版となったので良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 001 解説をご覧下さい.
■C++版プログラム(問題D/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 87 88 89 90 91 92 93 94 95 96 |
#include <bits/stdc++.h> using namespace std; using P = pair<int, 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 vector<string> vs, ans; vector<P> vp; int rain[2020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); // 2. 雨の降っていた時刻を集計. rep(i, N){ char c[11]; scanf("%s", c); string s(c); vs.pb(s); } // for(auto &p : vs) printf("%s\n", p.c_str()); // 3. 丸め処理. for(auto &c : vs){ // printf("%s\n", c.c_str()); // 時刻 -> 秒. // 開始. int s = 60 * (10 * (c[0] - '0') + (c[1] - '0')) + (10 * (c[2] - '0') + (c[3] - '0')); int sr = s % 10; s -= sr; if(sr >= 5) s += 5; // 終了. int e = 60 * (10 * (c[5] - '0') + (c[6] - '0')) + (10 * (c[7] - '0') + (c[8] - '0')); int er = e % 10; e -= er; if(er > 0 && er <= 5) e += 5; if(er > 5) e += 10; // いもす法. rain[s]++; rain[e + 1]--; } // 4. 累積和. rep(i, 2020) rain[i + 1] += rain[i]; // 5. 開始時刻, 終了時刻 を 保存. int s = -1, e = -1; rep(i, 2020){ if(rain[i] > 0){ if(s == -1) s = i, e = s; else e++; }else{ if(e - s > 0) vp.pb({s, e}); s = -1; e = -1; } } // for(auto &p : vp) printf("%d %d\n", p.a, p.b); // 6. フォーマット整理. for(auto &p : vp){ char s0 = p.a / 60 / 10 + '0'; char s1 = p.a / 60 % 10 + '0'; char s2 = p.a % 60 / 10 + '0'; char s3 = p.a % 60 % 10 + '0'; char e0 = p.b / 60 / 10 + '0'; char e1 = p.b / 60 % 10 + '0'; char e2 = p.b % 60 / 10 + '0'; char e3 = p.b % 60 % 10 + '0'; string s = ""; s.pb(s0); s.pb(s1); s.pb(s2); s.pb(s3); s.pb('-'); s.pb(e0); s.pb(e1); s.pb(e2); s.pb(e3); ans.pb(s); } // 7. 出力. for(auto &p : ans) printf("%s\n", p.c_str()); 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 |
[入力例] 4 1148-1210 1323-1401 1106-1123 1129-1203 [出力例] 1105-1210 1320-1405 ※AtCoderテストケースより [入力例] 1 0000-2400 [出力例] 0000-2400 ※AtCoderテストケースより [入力例] 6 1157-1306 1159-1307 1158-1259 1230-1240 1157-1306 1315-1317 [出力例] 1155-1310 1315-1320 ※AtCoderテストケースより [入力例] 5 0001-0005 0005-0009 0058-0058 0055-0059 0105-0105 [出力例] 0000-0010 0055-0100 |
■参照サイト
AtCoder Beginner Contest 001