けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 281 C - Circular Playlist (灰色, 300 点)

「割り算を使う」「ある値が 0 以下になるまで繰り返す」といった典型処理要素を詰め込んだ問題ですね!

問題概要

 N 曲からなるプレイリストがあり、曲には  1, \dots ,N の番号が付けられています。各曲の長さは  A_{1}, A_{2}, \dots, A_{N} です。

プレイリストを再生すると、曲  1, 2, \dots, N の順に流れます。曲  N が流れ終わると、再び曲  1 から順に流れていきます。

プレイリストを再生してから  T 秒後に流れているのはどの曲ですか? また、その曲が流れ始めてから何秒の時点ですか?

ただし、 T 秒後ちょうどに曲が切り替わるような入力は与えられません。

制約

  •  1 \le N \le 10^{5}
  •  1 \le T \le 10^{18}
  •  1 \le A_{i} \le 10^{9}

考えたこと

愚直には、次のコードのような解法が思い浮かびそうですね。最初は  T 秒間あった「残り時間」が徐々に減っていき、0 秒以下になる瞬間を捉えるコードです。

HP が  T のモンスターに対して、攻撃力が  A_{1}, A_{2}, \dots, A_{N} であるような  N 人が順に攻撃していって、モンスターの 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];
    }
}

しかしこのままでは、最悪計算量が大変なことになります!

  •  T = 10^{18}
  •  N = 1
  •  A = (1)

のようなとき、while 文を  10^{18} 回も反復してしまいます。このままでは TLE となります。

割り算の登場!

そこで割り算の登場です!  N 曲の長さの総和を  S としましょう。つまり、

 S = A_{1} + A_{2} + \dots + A_{N}

とします。そして、 T S で割り算します。

 T \div S = q あまり  r

とすると、 N 曲を  q ターン流したあと、残り  r 秒でラストターンに入ることになります。

たとえば

  •  T = 100
  •  N = 4
  •  A = (5, 9, 10, 3)

のとき、下図のようになります。

解法としては、 T をあらかじめ  S で割っておき、ラストターンのみ、for 文を回すようにします。そうすることで、計算量は  O(N) となります。

コード

#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];
    }
}