B - マラソン大会 / Marathon Editorial by MMNMM


\(\dfrac{\sum _ {i=1} ^ {k-1}D _ i}V\lt T _ k\) が成り立つか判定する際に、整数の切り捨て除算を使うことで \(64\) bit 整数だけを使って正しく判定することができます。

実数 \(r\) と整数 \(n\) に対して、\(r\lt n\iff\lfloor r\rfloor\lt n\) が成り立つことが示せます(\(\lfloor r\rfloor\) の定義より、\(\lfloor r\rfloor\le r\lt\lfloor r\rfloor+1\) が成り立ちます。\(\lfloor r\rfloor\le r\lt n\) なので \(r\lt n\implies\lfloor r\rfloor\lt n\) が、\(r\lt\lfloor r\rfloor+1\leq n\) なので \(r\lt n\impliedby\lfloor r\rfloor\lt n\) が成り立ちます)。

よって、\(\dfrac{\sum _ {i=1} ^ {k-1}D _ i}V\lt T _ k\) は \(\left\lfloor\dfrac{\sum _ {i=1} ^ {k-1}D _ i}V\right\rfloor\lt T _ k\) によって判定することができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <numeric>
#include <ranges>
using namespace std;

int main() {
    long N, V;
    cin >> N >> V;

    vector<long> D(N - 1), T(N - 1);
    for (auto&& d : D)
        cin >> d;
    for (auto&& t : T)
        cin >> t;

    inclusive_scan(D.begin(), D.end(), D.begin()); // 累積和を求める

    vector<int> ans; // 答えを入れる配列
    for (const auto& [i, p] : views::zip(D, T) | views::enumerate) {
        const auto& [d, t] = p;
        if (d / V < t) // d / V < t なら答えに追加する
            ans.emplace_back(i + 2);
    }

    if (ans.empty()) // ひとつもなければ
        cout << -1; // -1 を出力
    else
        for (const auto a : ans)
            cout << a << " ";
    cout << endl;
    return 0;
}

posted:
last update: