今日の精進（AtCoder ABC319-E）

今日の解き直した問題は AtCoder ABC319-E「Bus Stops」です。

問題

E - Bus Stops

ポイント

• $${1 \leq P_i \leq 8}$$ が制約として保証しているので、$${1}$$ から $${8}$$ の最小公倍数である $${840}$$ を移動時間の周期として、あらかじめ計算できそう。

• それでも移動時間の計算のところの計算量が $${100,000 * 840}$$ で $${80,000,000}$$ くらいになるが、実行時間制限が $${3}$$ sec なので、まぁなんとかなるか。

つまずいたところ

移動時間は $${840}$$ が周期なので、スタート時間が $${0 \sim 839}$$ まで、それぞれの移動時間を計算すればいいのだが、これが難しかったです。
移動時間の計算は以下のように実装しました。

vector<ll> res(840);
rep(i, 840) {
  ll now = i + X;
  rep(j , N-1) {
    while(now % P[j] != 0) {
      now++;
    }
    now += T[j];
  }
  now += Y;
  res[i] = now - i; // <-- ここで i を引くのを忘れない
}

最後の行の i を引くところがなかなか気がつかなかったので、次回解き直すときも忘れそうだなぁ。

ACできたのですが…

提出 #49267825 - AtCoder Beginner Contest 319

上のコードでACはできましたが、実行時間は $${2183}$$ ms でした。他の方の実行時間をみますと、$${1000}$$ ms かかっていない提出ばかりです。ということで、上のコードを見直しますと、while文が気になります。最大 $${8}$$ だからまぁいいかと思っていましたが、よく考えると無視できない量ですね（上のポイントでは無視しているのですが…）。これはwhile文で繰り返さなくても計算できるので、以下のように実装し直します。

vector<ll> res(840);
rep(i, 840) {
  ll now = i + X;
  rep(j , N-1) {
    now = (now + P[j] - 1) / P[j] * P[j];
    now += T[j];
  }
  now += Y;
  res[i] = now - i;
}

改善してACしたコード

提出 #49269765 - AtCoder Beginner Contest 319

改善した上のコードで提出し、実行時間は $${767}$$ ms でした。
次回もがんばります。