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:
