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文を太字にして