Medical Checkup [ICPC2017 アジア予選C]

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ICPCOOC2017&pid=C

N人の受診者がいる。
i番の受診者は検査を1つ受けるのにH[i]分かかる。
1番目の受診者から順番に検査1から順に受けていく。
各検査は1人ずつしか受けられない。
T分経ったあと、N人の受診者はそれぞれどの検査を受けているか
（待っている場合はどの検査を待っているか）
　
分かりにくいだろうのでサンプル1だけ図示しておく。

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15*	16*	17*	18*	19*	20*
1	1	1	1	1	2	2	2	2	2	3	3	3	3	3	4	4	4	4	4
w	w	w	w	w	1	1	1	1	1	1	1	2	2	2	2	2	2	2	3
w	w	w	w	w	w	w	w	w	w	w	w	1	1	1	w	w	w	w	2

このようになる。2番目と3番目の人はそれぞれ検査中なので、3,2を答える。
1番目の人は丁度4が終わった所だが、5を待機中と考えて5と答える。

解法

http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2650932&cid=ICPCOOC2017

2つの変数を持ちながら、1番目の人から順番にシミュレートしていく。
atop := 1番目の検査（検査A）が始まる時間
blast := 2番目の検査（検査B）が終わる時間
　
i番目の人が検査を始める時、atopから検査Aを始める。
次に検査Bを始めるが、これは前の人の検査Bが終わっている必要がある。
そのため、「btop := 2番目の検査が始まる時間」はbtop = max(atop + H[i], blast)となる。
この時、検査Aは待ち時間も含めると処理時間lenは「len = btop - atop」となる。
それ以降の検査B,検査C,...もそれだけの時間だけかかると考える（未証明）。
（同じような状態が続くので、なんとなく同じだけの時間かかりそうな感じがある）
後は残り時間restで何回検査できるかを計算。
　
注意するべきなのが、最後にd分だけ残った時にlen分の時間は無くてもH[i]分の時間はある場合がある。
その場合は出来る検査の回数が1回増える。

typedef long long ll;
int N; ll T, H[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> T;
    rep(i, 0, N) cin >> H[i];
 
    ll atop = 0, blast = 0;
    rep(i, 0, N) {
        ll btop = max(atop + H[i], blast);
        ll len = btop - atop;
        ll rest = T - atop;
 
        ll ans = 1;
        if (0 < rest) {
            ans = rest / len + 1;
            ll d = rest % len;
            if (H[i] <= d) ans++;
        }
 
        printf("%lld\n", ans);
 
        atop += H[i];
        blast = btop + H[i];
    }
}