Namaran

Code daily. Without assist.

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 になります。