SRM616 Div.1 250

コードが書きたい気分だった。

一番遅いstart+periodのlcmまでシミュレートすればよい。

(一番遅いstart時点でのsleep) > (一番遅いstart+全部のperiodのlcmの時点でのsleep)の場合

どんだけ開始時のSleepが大きくても周期ごとに減っていくのでそのうち起きる

それ以外の場合

シミュレートした区間内でのsleepの最小値が負の場合

開始時にminSleep*-1以下であれば起きる=>-1*minSleep

そうでない場合

0でないと起きない=>0

class WakingUp {
public:
    int maxSleepiness( vector <int> period, vector <int> start, vector <int> volume, int D ) {
        // BEGIN CUT HERE
#ifdef DEBUG
        DebugBreak();
#endif
        // END CUT HERE
        // calc lcm for all period
        int frequency = 1;
        int n = period.size();
        for(int i=0;i<n;++i){
            frequency = lcm(frequency, period[i]);
        }

        //simulate until the largest start time
        int sleep = 0;
        int minSleep = 1 << 30;
        int lastStartTime = *(max_element(start.begin(), start.end()));
        for(int i=1;i<=lastStartTime;++i){
            sleep += D;
            for(int j=0;j<n;++j){
                if(i >= start[j] && (i - start[j]) % period[j] == 0){
                    sleep -= volume[j];
                }
            }
            minSleep = min(sleep, minSleep);
        }

        int sleepAtLastStartTime = sleep;
        for(int i=0;i<frequency;++i){
            sleep += D;
            for(int j=0;j<n;++j){
                if(((lastStartTime + i + 1) - start[j]) % period[j] == 0){
                    sleep -= volume[j];
                }
            }
            minSleep = min(sleep, minSleep);
        }
        cerr << "sleepAtLastStartTime:" << sleepAtLastStartTime << endl;
        cerr << "minSleep:" << minSleep << endl;
        int ret;
        if(sleepAtLastStartTime <= sleep){
            if(minSleep < 0){
                ret = -1 * minSleep;
            }else{
                ret = 0;
            }
        }else{
            ret = -1;
        }
        return ret;
    }

    static int lcm(int x, int y){
        return x / gcd(x, y) * y;
    }

    static int gcd(int x, int y){
        return y == 0 ? x : gcd(y, x % y);
    }
};