「割り算を使う」「ある値が 0 以下になるまで繰り返す」といった典型処理要素を詰め込んだ問題ですね!
問題概要
曲からなるプレイリストがあり、曲には の番号が付けられています。各曲の長さは です。
プレイリストを再生すると、曲 の順に流れます。曲 が流れ終わると、再び曲 から順に流れていきます。
プレイリストを再生してから 秒後に流れているのはどの曲ですか? また、その曲が流れ始めてから何秒の時点ですか?
ただし、 秒後ちょうどに曲が切り替わるような入力は与えられません。
制約
考えたこと
愚直には、次のコードのような解法が思い浮かびそうですね。最初は 秒間あった「残り時間」が徐々に減っていき、0 秒以下になる瞬間を捉えるコードです。
HP が のモンスターに対して、攻撃力が であるような 人が順に攻撃していって、モンスターの HP が 0 以下になる瞬間を捉えるようなイメージです!
while (T > 0) { for (int i = 0; i < N; ++i) { if (T - A[i] <= 0) { cout << i + 1 << " " << T << endl; return 0; } T -= A[i]; } }
しかしこのままでは、最悪計算量が大変なことになります!
のようなとき、while
文を 回も反復してしまいます。このままでは TLE となります。
割り算の登場!
そこで割り算の登場です! 曲の長さの総和を としましょう。つまり、
とします。そして、 を で割り算します。
あまり
とすると、 曲を ターン流したあと、残り 秒でラストターンに入ることになります。
たとえば
のとき、下図のようになります。
解法としては、 をあらかじめ で割っておき、ラストターンのみ、for
文を回すようにします。そうすることで、計算量は となります。
コード
#include <bits/stdc++.h> using namespace std; int main() { long long N, T; cin >> N >> T; // N 曲の長さを入力として受け取りながら総和を求める long long S = 0; vector<long long> A(N); for (int i = 0; i < N; ++i) { cin >> A[i]; S += A[i]; } // T を「T を S で割ったあまり」に置き換える T %= S; // ラストターン for (int i = 0; i < N; ++i) { if (T - A[i] <= 0) { cout << i + 1 << " " << T << endl; return 0; } T -= A[i]; } }