ICPC2017 Asia Regional Tsukuba C Medical Checkup

問題

とても読みにくい問題文。


n人の人がt秒以内に機械(m1, m2, m3, ...)を使う。

  • 同時に一人一個の機械しか使えず、一つの機械は同時に一人でしか使えない
  • 各人はm1から順にとばさずに機械を使う必要がある
  • 各機械は、1番目の人から順に使用する。i番目の人の使用が終わったら即座にi+1番目の人に渡す
  • i番目の人が機械を使うとき、どの機械もh[i]の時間がかかり、中断はできない
  • 機械を渡された人が別の機械を使用中のとき、渡された機械はその人がその前の機械を全て使い終わってから(即座に)使い始める

このとき、各人が何個目の機械を使用中、あるいは何個目の機械を待っている状態であるかを求めよ。t秒の時点でちょうど機械を使い終わった場合、次の機械を待っている状態であるとする。

制約条件

n≦10万
h[i], t≦10^9

解法

それぞれの人が機械m1, m2, m3, ...を使い終わる時刻は必ず等差級数になっているというのが重要な考察。
それぞれの人が最初の機械m1を渡される時刻および、機械が渡される間隔がわかっていれば、その人が機械を何個使えるかおよび、次の人にm1がわたる時刻と機械が渡される間隔もわかる。

ソースコード

int main(){
	int n, t; cin >> n >> t;
	vi h(n);
	rep(i, n) cin >> h[i];
	
	ll start = 0, interval = 0, count = inf;
	rep(i, n){
		start += h[i];
		interval = max(interval, (ll)h[i]);
		
		ll nct = (t - start) / interval + 1;
		if(start > t) nct = 0;
		
		count = min(count, nct);
		cout << count + 1 << endl;
	}
	return 0;
}