2026-09-28
occupancy.cpp
#include <numeric>
#include <vector>
struct Stay {
int in, out;
};
std::vector<int> occupancy(int days, const std::vector<Stay> &stays) {
std::vector<int> d(days + 1);
for (auto [in, out] : stays) {
++d[in];
--d[out];
}
std::adjacent_difference(d.begin(), d.end(), d.begin());
d.pop_back();
return d;
}
宿泊の記録 {チェックイン日, チェックアウト日} から、0 日目から days - 1 日目までの各日の宿泊者数を求める occupancy です。チェックアウト日は泊まった日に数えません。occupancy(5, {{0, 3}, {2, 5}}) の結果を空白区切りで出力すると、いまは 1 -1 1 -2 1 になりますが、本来は 1 1 2 1 1 です。どこを直せばよいでしょうか?
Answer
std::adjacent_difference を std::partial_sum に変えます。
ループのあとの d は {1, 0, 1, -1, 0, -1} で、各日に宿泊者数が前日からいくつ増減したかを表しています。人数に戻すには、この増減を0日目から足し上げる累積和が要ります。
std::adjacent_difference は逆に、隣り合う要素の差 d[i] - d[i - 1] を並べます。人数の列から差分配列を作るときに使う関数なので、差分配列に使うと差の差が並び、1 -1 1 -2 1 のように人数としてありえない負の値まで出てきます。std::partial_sum なら先頭から 1, 1, 2, 1, 1, 0 と累積され、最後の 0 を pop_back で捨てて 1 1 2 1 1 になります。