torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder SRM 616, Division 2, Level 1 : WakingUpEasy

問題概要

 アレックスの眠気は、整数によって特徴付けられる。
 今、いくつかのアラームが鳴ろうとしていて、アラームによってアレックスの眠気が変化する。アラームのリスト volumes が与えられる。voluimes[ i ] は i 番のアラームの音量を表す。単位時間あたりにリストの先頭にある一つのアラームが鳴り、その後アラームはリストの末尾に移動される。このとき、アレックスの眠気はそのアラームの音量の分だけ減少する。
 アレックスは、眠気が 0 以下になったときに目覚める。アレックスの初期状態での眠気 S が与えられるので、アレックスが目覚めるまでにかかる時間を求めよ。

解法

 アラームの個数を N とします。
 ある時間 t に鳴るアラームの番号は、volumes[ t mod N ] と表せます。また、アレックスの眠気の最大値が 10,000 なので、目覚めるまでにアラームが鳴る回数も高々 10,000 です。この程度ならば愚直にシミュレーションしても十分間に合います。すなわち、時刻 t に関してループを回しつつ S を更新する処理を 0 < S である間繰り返し、 ループが回った回数を return することで解くことができます。

コード

class WakingUpEasy
{
public:
	int countAlarms(vector <int> volume, int S)
	{
		int res = 0;
		for ( int i = 0; 0 < S; S -= volume[ i++ % volume.size() ], res++ );
		return res;
	}
};