愚直にシミュレーションを行うと、最大で \(O(T)\) 回の曲の切り替わりが発生するため、実行時間制限に間に合いません。そこで、周期性を利用します。

\(S = A_1 + \dots + A_N\) とおきます。プレイリストを再生してから \(S\) 秒後には、再び曲 \(1\) が流れ始めます。よって、\(T_0 \geq S\) のとき、\(T = T_0\) のときの答えと \(T = T_0 - S\) のときの答えは同じであることがわかります。これを繰り返し用いることで、\(T\) を \(S\) で割った余りを考えれば、\(T \lt S\) の場合に帰着することができます。

\(T \lt S\) の場合、愚直にシミュレーションを行っても最大 \(N-1\) 回しか曲の切り替わりは起きません。よって、この問題を \(O(N)\) で解くことができました。

実装例 (C++)