今日の精進(AtCoder ABC319-E)
今日の解き直した問題は AtCoder ABC319-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できたのですが…
上のコードで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したコード
改善した上のコードで提出し、実行時間は $${767}$$ ms でした。
次回もがんばります。
この記事が気に入ったらサポートをしてみませんか?