トップ > JOI精進録 > [JOI精進録] 難易度8「安全点検」(JOI2020/2021 二次予選D)
最終更新日

[JOI精進録] 難易度8「安全点検」(JOI2020/2021 二次予選D)

JOI精進録

難易度8初ACです。

問題リンク

atcoder.jp

問題概要

K人の人がいる。彼らは1分間で以下の行動を1回できる。
・距離1だけ移動する
・今いる座標の施設で1回作業する
N個の施設があり、座標A_i (1 \le i \le N)に施設があります。 B_i (1 \le i \le N)回の作業をそれぞれの施設で行うとき、すべて完了できるのは最短で何分必要ですか？

解説

最初の解法 (18/100点)

答えで二分探索をします。以降、二分探索の範囲0~1e18をr-lで1e18とし、Rと表記します。
判定関数をx秒で全ての作業を終えられるか、で設定します。
実装はk人ごとにx秒でまだ点検の完了していない一番遠い施設まで行き、できるだけ作業をします。
その施設の点検が完了してまだ秒数が残っている場合、途中の施設によって作業をしていたことにします。
計算量はO((K + N) log R)です。

提出結果

atcoder.jp

TLE1で落ちている...だと...

高速化を試みる (18/100点)

累積和と二分探索で高速化を試みました。
計算量はO(K log N log R)になりました。

提出結果

atcoder.jp

ひどくなりました。

あることに気づく

高速化の方法を間違えて計算量を悪化させていることにここでようやく気づきました。
そしてKが最大1e9で一番ネックになっているのでこのKをどうにかすれば良さそうです。

AC解法 (100/100点)

判定関数を工夫します。
x秒でK人を使って完了できるかという判定方法はO(K + N)となります。
視点を変えてx秒で作業を終わらせるには何人が必要か、という実装をすると施設iで必要な人数は除算で求められるのでO(N)で計算できます。
計算量はO(N log R)となりました。

ACコード

#include <bits/stdc++.h>
using namespace std;

int main(){
  long long n,k; cin >> n >> k;
  vector<long long> A(n),B(n),acc(n+1);
  for (long long& a:A) cin >> a;
  for (long long& a:B) cin >> a;
  int i(1);
  auto vi = views::iota(0ll,(long long)1e18);
  cout << *lower_bound(vi.begin(),vi.end(),0ll,[&A,&B,&k,&n](const long long& x, const long long& y){
    if (A.back()>=x) return true;
    long long i(-1),b(B.back());
    for (int j(n-1);j > -1;--j){
      long long u = x-A[j];
      i+=ceil((double)b/(double)u);
      b -= ceil((double)b/(double)u)*u;
      if (j>0&&b<1){
        while(j>0&&b<1) --j,b+=B[j];
        ++j;
      }
    }
    return (i>=k);
  }) << endl;
}

提出結果

atcoder.jp