\(i\) 番目の人がチケットを購入し終わるのが今から \(x_i\) 秒後だとします。また、便宜上 \(x_0=0\) とおきます。

各 \(i\ (1\leq i\leq N)\) について、\(x_i\) の値が \(x_{i-1}\) の値を用いてどのように表されるか考えます。

• \(x_{i-1} \leq T_i\) のとき：\(i\) 番目の人がチケット売り場を訪れたタイミングで列は存在しないので、すぐさま購入手続きを開始できます。よって、\(x_i=T_i+A\) です。
• \(x_{i-1} > T_i\) のとき：\(i\) 番目の人がチケット売り場を訪れたタイミングではまだ前の人たちがチケットを購入しているので、\(i\) 番目の人は \(i-1\) 番目の人が購入を終了し次第購入手続きを開始します。よって、\(x_i=x_{i-1}+A\) です。

これらをまとめると \(x_i=\max(x_{i-1},T_i)+A\) となります。よって、この式を用いて \(i=1,2,\dots,N\) の順に \(x_i\) の値を求めていけばよいです。

実装例 (C++) :

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, a;
    cin >> n >> a;
    int pre = 0;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        int ans = max(pre, t) + a;
        cout << ans << '\n';
        pre = ans;
    }
}

実装例 (Python) :

n, a = map(int, input().split())
t = list(map(int, input().split()))
pre = 0
for i in range(n):
    ans = max(pre, t[i]) + a
    print(ans)
    pre = ans