ABC001 D - 感雨時刻の整理


Tags:cpatcodergreedydiff_experimentaldiff_cyan

問題

https://atcoder.jp/contests/abc001/tasks/abc001_4

問題文

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

制約

  • 1N300001 \le N \le 30000
  • 時刻: 00000000 から 24002400

サンプル

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, r] で表現できる。
    • とりあえずソートする。
    • lnextrl_{\mathrm{next}} \le r であれば、連続しているとみなせるので、 r=max(r,rnext)r = \max(r, r_{\mathrm{next}}) とする。
    • そうでなければ、これまでの [l,r][l, r] を答えに入れて、 l=lnext,r=rnextl = 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;
}