SRM616 div1 easy WakingUp

考えたこと

とりあえず周期性がありそう。全てのアラームが鳴るタイミングまで進めばあとは周期lcmで繰り返されそう。10以下の整数のlcmは5*7*8*9=2520で計算量的には問題なさそう。周期の部分が負なら必ず起きそうなので-1を返すことにする。サンプル3で全てのアラームが鳴るタイミングが求められない。よくよく考えるとそもそも鳴るタイミングの偶奇が一致しないパターンも存在するし全てのアラームが鳴るタイミングがないパターンがある。このあたりを例外処理したつもりの怪しいコードを書いて出してみる。案の定落ちる。
解説記事を読むとそもそも全てのアラームが鳴るタイミングまで進まなくても周期lcmの周期性があるらしい。言われてみれば自明。imosを使ってシミュレーションを書くと通った。

学び

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

ll gcd(ll a, ll b) {
  return b != 0 ? gcd(b, a%b) : a;
}
ll lcm(ll a, ll b) {
  return a/gcd(a, b)*b;
}

int imos[3010];
class WakingUp {
   public:
   int maxSleepiness(vector<int> p, vector<int> s, vector<int> v, int D)
  {
    int n = p.size();
    memset(imos, 0, sizeof(imos));
    REP(i, n) {
      int j=s[i];
      while(j<2521) imos[j]-=v[i], j+=p[i];
    }
    FOR(i, 1, 2521) imos[i] += D;
    FOR(i, 1, 2521) imos[i] += imos[i-1];
    if(imos[2520] < 0) return -1;
    int ret = INF;
    FOR(i, 1, 2521) chmin(ret, imos[i]);
    if(ret >= 0) return 0;
    else return abs(ret);
  }
};