D - 感雨時刻の整理

問題

https://atcoder.jp/contests/abc001/tasks/abc001_4 (新しいタブで開く)

問題文

メモが与えられるので、「時系列順・5 分丸め・連続するものはまとめる」で整理して出力してね。

制約

• $1 \le N \le 30000$
• 時刻: $0000$ から $2400$

サンプル

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 にソートして、連続するものをまとめる。

ポイント

1. 前の時刻は切り捨て、後ろの時刻は切り上げの部分
   • 切り捨ては、 mod 5 で 0 になるように引く。つまり、 x - (x % 5) 。
   • 切り上げは、 mod 5 で 0 になるように足す。つまり、 x + ((5 - (x % 5)) % 5) 。
   • 切り上げ時に 60 になったら 1 時間足すのを忘れずにする (1 WA した (新しいタブで開く))
2. 連続値まとめ
   • 時間は 区間 $[l, r]$ で表現できる。
   • とりあえずソートする。
   • $l_{\mathrm{next}} \le r$ であれば、連続しているとみなせるので、 $r = \max(r, r_{\mathrm{next}})$ とする。
   • そうでなければ、これまでの $[l, r]$ を答えに入れて、 $l = l_{\mathrm{next}}, r = r_{\mathrm{next}}$ として次の区間を見る。
   • 最後にも答えに入れるのを忘れずに

コード

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;
}