TopCoder SRM 616, Division 1, Level 1 : WakingUp

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13124&rd=15849

問題概要

　アレックスの眠気は、整数によって特徴付けられる。アレックスの眠気は、単位時間あたり D だけ増加する。
　更に、今、いくつかのアラームが鳴ろうとしていて、アラームによってアレックスの眠気が変化する。i 番のアラームは start[ i ] + k * period[ i ] ( k = 0, 1, 2, ... ) に voluime[ i ] の音量で鳴る。このとき、アレックスの眠気は volume[ i ] だけ減少する。また、複数のアラームが同時に鳴った場合は、その音量の合計だけアレックスの眠気が減少する。
　アレックスは、眠気が 0 以下になったときに目覚める。十分な時間が経過したときにアレックスが目覚めることができる初期の眠気であって、値が最大となるものを求めよ。無限に大きく出来る場合は -1 で示せ。

解法

　眠気の初期状態からに変位が重要なので、初期値 0 としてシミュレーションすることを考えます。解が有界である場合、適当な経過時間までシミュレーションをして、出現する眠気の最小値を正負反転したものを答えとすることで解くことができます。そうでないときは、シミュレーション時間を更に伸ばすことでよりよい解を得られるはずです。従って、シミュレーションした全ての時間を半分で区切って、前半で得られる最小値より小さな値を後半で得られるならば　-1 とする、などの方法で判別することができます。

コード

using VI = vector<int>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

constexpr int SIM_NUM = 10000;

class WakingUp
{
public:
	int maxSleepiness(vector <int> period, vector <int> start, vector <int> volume, int D)
	{
		const int N = period.size();

		VI vs( SIM_NUM );
		REP( i, 0, N )
		{
			for ( int t = start[i]; t < SIM_NUM; t += period[i] )
			{
				vs[t] += volume[i];
			}
		}

		VI ss( SIM_NUM );
		REP( i, 1, SIM_NUM )
		{
			ss[i] = ss[ i - 1 ] + D - vs[i];
		}

		const int res = *min_element( ss.begin(), ss.begin() + SIM_NUM / 2 );
		return *min_element( ALL( ss ) ) < res ? -1 : -res;
	}
};