D - 感雨時刻の整理

cpatcodergreedydiff experimentaldiff cyan

最終更新日

Table of Contents

Loading...

問題

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

ポイント

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