AOJ 2236 Rabbit Plays Games!

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2236

主人公とn人の敵がいる. 各々HP, ATK, DEF, SPD のステータスを持つ.

ターン制で先頭を行い, 各ターンではSPDの高い順に攻撃を行う.

キャラi(主人公/敵) がキャラj に攻撃する時, 相手のHPをmin(0, ATK_i - DEF_j)減少させる.

各ターンで主人公が攻撃する相手を適切に定め, その時主人公の受けるダメージの最小値を出力せよ. (主人公のHPを超える時は-1)

1<=n<=40000, 1<=h, a, d, s<=1,000,000,000 (s は distinct)

解法

どの順番で敵を倒すか考える.

敵i を倒すのに必要なターン数 turn[i], 1ターンでその敵から受けるダメージを dmg[i] とする.

敵i, j のどちらを先に倒すべきかだが, i を先に倒す場合は turn[i] * dmg[j], j を先に倒す場合には turn[j] * dmg[i] だけ受けるダメージが増えることを考えると turn[i]/dmg[i] が小さい順に倒せば良いことが分かる. (すぐ倒せ, 受けるダメージが大きい方を先に倒すと嬉しそう)

JAG の解説スライドに書かれていない本質があって,
1. 主人公にダメージを与えられない敵は無視(一番最後に回す)
2. 主人公がダメージを与えられない敵(1. を満たす場合は除外)がいる場合は-1
3. 戦闘が終了しないようなテストケースが含まれている.(1WA, 主人公も敵もダメージを与えられない場合) 問題文をよく読むとどう出力すべきかは分かるが…

主人公のHPが無くなったらすぐreturnしないと実装によってはアンダーフローするかも.

ソースコード

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3619635#1

#include "bits/stdc++.h"
using namespace std;
using ll = long long;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    ll hp, atk, def, spd;
    cin >> hp >> atk >> def >> spd;
    vector<ll> h, a, d, s;
    for (int i = 0; i < n; i++)
    {
        ll htmp, atmp, dtmp, stmp;
        cin >> htmp >> atmp >> dtmp >> stmp;
        if (dtmp >= atk && atmp > def)
        {
            cout << -1 << endl;
            return 0;
        }
        if (atmp <= def)
            continue;
        atmp -= def;
        h.push_back(htmp);
        a.push_back(atmp);
        d.push_back(dtmp);
        s.push_back(stmp);
    }
    n = h.size();
    vector<ll> turn(n);
    for (int i = 0; i < n; i++)
    {
        ll tmp = atk - d[i];
        turn[i] = (h[i] - 1) / tmp + 1;
    }
    vector<int> idx(n);
    for (int i = 0; i < n; i++)
        idx[i] = i;
    sort(idx.begin(), idx.end(), [&](int i, int j) { return turn[i] * a[j] < turn[j] * a[i]; });
    ll ret = 0, cnt = 0;
    for (auto i : idx)
    {
        hp -= cnt * a[i];
        ret += cnt * a[i];
        cnt += turn[i];
        if (s[i] <= spd)
            turn[i]--;
        hp -= turn[i] * a[i];
        ret += turn[i] * a[i];
        if (hp <= 0)
        {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << ret << endl;
}

感想

問題文のラスト1文を太字にして