kmjp's blog

競技プログラミング参加記です

TopCoder SRM 616 Div1 Easy WakingUp

SRM616に参加。久々にEasy/Mediumを解いて好順位につけた。
おかげで次回Mediumを解けば赤文字になれそう。
http://community.topcoder.com/stat?c=problem_statement&pm=13124

問題

初期状態の眠さを整数Sとする。
この眠さは時間1につきD増加する。

ここにN個の時計がある。
各時計は初回時刻start[i]、以後時間period[i]ごとにアラームをならし、その都度眠さがvolume[i]減少する。
眠さが0以下になると目を覚ますことになる。

最終的に目を覚ますことができる最大の初期状態の眠さSを答えよ。

解法

period[i]は1~10なので、時間LCM(1,2,...,10)=8*9*5*7=2520ごとに時計の動作は周期性がある。
よって時間2520分シミュレートし、初期状態より眠気が減少するなら、無限の時間があればどんなSでも最終的に目を覚ます。

1周当たりで眠気が覚めない場合、1周の間で眠気が最小化するときのの眠さと初期状態の眠さの差が答え。
以下の答えでは律儀に周期を求めているが、どうせどんなperiod[i]でも2520の約数が周期なのでper=2520で固定しても良い。

class WakingUp {
	public:
	int maxSleepiness(vector <int> period, vector <int> start, vector <int> volume, int D) {
		int N=period.size();
		int i,x,y;
		ll per=1;
		FOR(i,N) {
			ll g=__gcd(per,(ll)period[i]);
			per=per*period[i]/g;
		}
		ll cur=0;
		ll ma=0;
		for(i=1;i<=per;i++) {
			cur+=D;
			FOR(x,N) if(i>=start[x]&&(i-start[x])%period[x]==0) cur-=volume[x];
			if(cur<0) ma=max(ma,-cur);
		}
		if(cur<0) return -1;
		return ma;
	}
};

まとめ

本番、周期性があることにさらっと気づけたのはよかった。