問題
https://atcoder.jp/contests/abc001/tasks/abc001_4 (新しいタブで開く)
問題文
メモが与えられるので、「時系列順・5 分丸め・連続するものはまとめる」で整理して出力してね。
制約
- 時刻: から
サンプル
I/O 1
4
1148-1210
1323-1401
1106-1123
1129-1203
1105-1210
1320-1405
I/O 2
1
0000-2400
0000-2400
I/O 3
6
1157-1306
1159-1307
1158-1259
1230-1240
1157-1306
1315-1317
1155-1310
1315-1320
考察
これは実装が面倒だけど、丸めて、Greedy にソートして、連続するものをまとめる。
ポイント
- 前の時刻は切り捨て、後ろの時刻は切り上げの部分
- 切り捨ては、 mod 5 で 0 になるように引く。つまり、
x - (x % 5)
。 - 切り上げは、 mod 5 で 0 になるように足す。つまり、
x + ((5 - (x % 5)) % 5)
。 - 切り上げ時に 60 になったら 1 時間足すのを忘れずにする (1 WA した (新しいタブで開く))
- 切り捨ては、 mod 5 で 0 になるように引く。つまり、
- 連続値まとめ
- 時間は 区間 で表現できる。
- とりあえずソートする。
- であれば、連続しているとみなせるので、 とする。
- そうでなければ、これまでの を答えに入れて、 として次の区間を見る。
- 最後にも答えに入れるのを忘れずに
コード
https://atcoder.jp/contests/abc001/submissions/27938651 (新しいタブで開く)
int main() {
int n;
cin >> n;
vector<pair<int, int>> v;
rep(i, n) {
int a, b;
scanf("%d-%d", &a, &b);
// 丸める
a = a - (a % 5);
b = b + (5 - (b % 5)) % 5;
if (b % 100 >= 60) b += 40;
v.push_back({ a, b });
}
// まとめる
sort(v.begin(), v.end());
vector<pair<int, int>> ans;
pair<int, int> prev = v[0];
rep(i, n) {
if (prev.second < v[i].first) {
ans.push_back(prev);
prev = v[i];
}
else {
prev.second = max(prev.second, v[i].second);
}
}
ans.push_back(prev);
// 出力
rep(i, ans.size()) {
printf("%04d-%04d\n", ans[i].first, ans[i].second);
}
return 0;
}