けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 368 C - Triple Attack (4Q, 灰色, 300 点)

シミュレーション シミュレーション:繰り返し回数を割り算で求める 周期性に着目する AtCoder AtCoder300点 ABC-C 灰色diff 数列 敵やモンスターのHPを削って倒していく問題 NoviSteps4Q 計算量改善:繰り返し回数を割り算で求める 易しい計算量改善

完全な愚直シミュレーションでは通らなくて、割り算で繰り返し回数を求める系の問題！

問題概要

N 体の敵を順に倒す。 i 体目の敵の HP は H_{i} である。

あなたは 0 に初期化された変数 T を管理している。敵を攻撃するとき、次のようにする。

  • T を 1 増やす
  • その後、 T が 3 の倍数ならば敵の HP を 3 減らし、そうでなければ敵の HP を 1 減らす
  • 敵の HP が 0 以下になったら終了する

すべての敵の HP を 0 以下にしたときの T の値を求めよ。

制約

  • 1 \le N \le 2 \times 10^{5}
  • 1 \le H_{i} \le 10^{9}

考えたこと

完全な愚直シミュレーションでは TLE してしまう。つまり、毎回 T を 1 増やしながら敵の HP を 1 または 3 ずつ削るシミュレーションを書く解法が考えられるが、それでは TLE してしまう。

そこで、次の部分問題を効率的に解く方法を考えよう。

初期値 T が与えられる。

このとき HP が H である敵を倒したときの T の値を求めよ。

ここで注目したいことは、 T がいかなる値であったとしても、「3 回攻撃したら敵の HP を 1 + 1 + 3 = 5 ずつ減らす」ということである。最初の T を 3 で割った余りが 0 であっても、1 であっても、2 であっても、その状態から 3 回攻撃したら敵に与えるダメージは 5 なのである。

そこで、 T を 5 で割ったときの商を q、余りを r とすると、次のように言える。

  • 3q 回の攻撃をして、敵の HP は r になる

最後は、 r = 0, 1, 2, 3, 4 のいずれかであるから、残り最後まで敵の HP を 0 以下のする部分は愚直なシミュレーションを書けば良い。

以上の解法は、各敵についての処理を O(1) で実行できるので、全体の計算量は O(N) となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    long long T = 0;
    for (int i = 0; i < N; i++) {
        long long H;
        cin >> H;
        T += (H / 5) * 3;
        H %= 5;

        while (H > 0) {
            T++;
            if (T % 3 == 0) H -= 3;
            else H--;
        }
    }
    cout << T << endl;
}