はまやんはまやんはまやん

hamayanhamayan's blog

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