Safety System [第六回 アルゴリズム実技検定 F]

https://atcoder.jp/contests/past202104-open/tasks/past202104_f

解説

https://atcoder.jp/contests/past202104-open/submissions/22645973

問題文で要求されている仕様も難しいが、ちゃんと読み解ければ実装はそれほど難しくない。

foreverとなる場合

自明なコーナーケースを見つけたら先に潰しておくことをお勧めする。
今回のようなできない場合というのがある場合は、どういった場合にそうなるのかを検討しておこう。
今回は負荷L以上の処理が連続T秒間に達した瞬間にコンピュータが停止するが、再開したら、タスクの始めに戻るので、ここでforeverになりそうな感じがする。
負荷がL以上で、連続T秒間を超えるタスクがあれば、foreverである。
そして、このようなタスクが無ければ、コンピュータが停止してしまうが、処理は終えることができる。

要求仕様を丁寧に実装していこう

丁寧に場合分けをして実装していこう。
現在の時間t, 負荷がかかっている時間fukaを保持しながらシミュレートしていく。

• 負荷がL未満の場合
  • 時間はA[i]だけ足されて、負荷がかかっている時間はリセットされる
• 負荷がL以上の場合
  • かつ、fuka+A[i]がT未満の場合は、単純に処理を行う
  • かつ、fuka+A[i]がちょうどTの場合は、処理を行った後に処理停止が発生するので処理停止させておく
  • かつ、fuka+A[i]がTを超える場合は、Tまで処理を行ったあと、処理停止をさせて、その後改めて処理を行う
    • ここで注意点があり、改めて処理を行うとまたTだけ時間がかかって処理停止が発生する場合があるので、その場合は処理停止処理を行う

int N, L, T, X, A[1010], B[1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> L >> T >> X;
    rep(i, 0, N) cin >> A[i] >> B[i];

    rep(i, 0, N) if (T < A[i] && L <= B[i]) {
        cout << "forever" << endl;
        return;
    }

    int t = 0;
    int fuka = 0;
    rep(i, 0, N) {
        if (B[i] < L) {
            t += A[i];
            fuka = 0;
        }
        else {
            if (fuka + A[i] < T) {
                t += A[i];
                fuka += A[i];
            }
            else if (fuka + A[i] == T) {
                t += A[i] + X;
                fuka = 0;
            }
            else {
                t += T - fuka + X + A[i];
                fuka = A[i];
                if (fuka == T) {
                    t += X;
                    fuka = 0;
                }
            }
        }
    }

    cout << t << endl;
}