SRM616 Div1 Easy "WakingUp"
問題
TopCoder Statistics - Problem Statement
訳
アレックスはぐっすり眠っている。1分おきに彼の眠気度を数値化することができる。スタートの0分における彼の眠気度Sは不明である。
不幸なことに、いくつかの繰り返し機能のある目覚まし時計が眠りを妨害しようとしている。
それぞれの1分間に次のようなことが起こる。まず始めにアレックスの眠気度はDだけ増加する。それから目覚まし時計のアラームが眠気度を減少させる。
正確には、アラームは与えられる3つのint period, start, volumeによって数値化されている。i番目のアラームはstart[i]分, start[i] + period[i]分, start[i] + period[i] * 2分... に鳴るようになっている。そしてアレックスの眠気度をvolume[i]だけ減少させる。もし複数のアラームが同じ時間に鳴れば、それらのボリュームの合計値だけ眠気度を減少させることになる。
眠気度が正であれば彼は眠っていることになる。一度0以下になれば、アレックスは即座に目を覚ます。アレックスの眠気度の初期値は正でない可能性もあり、そのような場合0分目に目を覚ますことに注意してほしい。
あなたはint period, start, volume そしてint Dが与えられる。彼がいつか起きることになるような、最も大きいS(彼の眠気度の初期値)を返せ。Sをいくら大きくしてもやがて目を覚ますようであれば-1を返せ。
制約
1 <= 目覚まし時計の数 <= 50
1 <= period[i] <= 10
1 <= start[i] <= period[i]
1 <= volume[i] <= 1000
1 <= D <= 100
考えたこと
アラームの間隔が1~10。1~10の公倍数の時間でアラーム鳴り方に周期性が現れることになりそう。というわけで、1~10の最小公倍数をとると2520。よし、シミュレートでいけそう。
2520秒で鳴るアラームのボリュームの合計値が、その間増加する眠気度を上回れば、Sが無限大になるパターンになる。
それ以外は周期ごとに見ると眠気度が増加するか、よくて横ばいなので最初の周期だけを気にすればよさそう。アラームの開始時間がバラバラなので2回試しとこ。
ソースコード
class WakingUp { public: int maxSleepiness(vector <int> period, vector <int> start, vector <int> volume, int D) { int n = period.size(); int loop = 2 * 2 * 2 * 3 * 3 * 5 * 7; long long sum = 0; for (int i = 0; i < n; i++) { sum += loop / period[i] * volume[i]; } if (D * loop < sum) return -1; int cul = 0; int res = 0; for (int i = 1; i < loop * 2; i++) { cul += D; for (int j = 0; j < n; j++) { if (i >= start[j] && ((i - start[j]) % period[j]) == 0) cul -= volume[j]; } res = max(res, -cul); } return res; } };