yukicoder No.9 モンスターのレベル上げ

No.9 モンスターのレベル上げ - yukicoder

問題概要

味方モンスター(レベルはそれぞれ )を以下の方法でレベル上げするとき、各味方モンスターのレベル上げ最大回数の最小を求める。

1. 最初に、円形に並んだ敵モンスターの始点を定める。
2. 始点から順(添字の昇順)に、以下を満たすように選ばれた味方モンスターのレベルを、敵モンスターのレベルの半分 だけ上げる。
3. 味方モンスターは、現時点でレベルが最小のものから任意に 匹選べる。
4. 敵モンスターを 周したら終了。

解法

愚直にシミュレーションする。優先度付きキューを利用して、レベルとレベル上げ回数が常に昇順になるようにしておく。

inline constexpr ll modulo(const ll n, const ll m) noexcept {
    if (n < 0) {
        return n % m + m;
    } else if (n >= m) {
        return n % m;
    } else {
        return n;
    }
}

int main() {
    ll N, res = INF;
    cin >> N;
    ll A[N], B[N];
    rep(i, N) cin >> A[i];
    rep(i, N) cin >> B[i], B[i] /= 2;
    rpriority_queue<pair<ll, ll>> P;
    rep(i, N) {
        rep(i, N) P.push({A[i], 0});
        rep(j, N) {
            ll id = modulo(i + j, N), lv, n;
            tie(lv, n) = P.top(), P.pop();
            P.push({lv + B[id], n + 1});
        }
        ll max = 0;
        while (P.size()) {
            ll lv, n;
            tie(lv, n) = P.top(), P.pop();
            chmax(max, n);
        }
        chmin(res, max);
    }
    cout << res << endl;
}