ferinの競プロ帳

競プロについてのメモ

AOJ2236 Rabbit Plays Games!

競技プログラミング 要復習 AOJ

問題ページ
Rabbit Plays Games! | Aizu Online Judge

考えたこと

  • 項目が多すぎるのでまとめたい
  • まず敏捷sについて関係あるのは自分より早く動くか遅く動くかだけ
  • 敏捷の差とか考えたくないので無視したい
  • 戦闘前に自分より早く動くやつにダメージをもらうとしておけば各ターンで自分が最初に動くとできる
  • 敏捷は考えなくてよくなった
  • 攻撃力と防御力があるが一々差を取るのは面倒
  • それぞれの敵について与えるダメージと食らうダメージを求めておく
  • 敵iに与えるダメージとHPがわかっていれば敵iを倒すのにかかるターン数が求まる
  • まとめると敵iから食らうダメージd[i]と倒すのにかかるターン数t[i]の2項目になった
  • ダメージが大きい順に倒したりターンが短い順に倒すような貪欲は反例が簡単に作れる
  • DPができるような制約ではないのでうまいこと貪欲とかできっちり決められるはず
  • 敵i→敵jの順で倒すとすると(t[i]-1)d[i] + (t[i]+t[j]-1)d[j]ダメージをもらう
  • 敵j→敵iの順で倒すとすると(t[j]-1)d[j] + (t[i]+t[j]-1)d[i]ダメージをもらう
  • 入れ替えると +t[j]d[i]-t[i]d[j] ダメージが変化する
  • 何かソートしたい気持ちになるけど隣接した要素間でしか大小比較ができない
  • 敵iと敵jの間に倒す敵がいると大小関係が狂う気がする
  • うまく順序を決められない
  • 他の貪欲とか二分探索とか考えるけどうまくいかない
    -----解説を読んだ-----
  • 倒す順番を変えると +t[j]d[i]-t[i]d[j]ダメージ変化しているはず
  • つまり t[j]d[i]-t[i]d[j] < 0
  • t[j]/d[j] < t[i]/d[i]
  • t[x]/d[x]が小さい順に倒すべき

ダメージを与えられないけどダメージをもらわない敵とかが存在するので注意
よくわかってないので後で解く

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

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

  int n;
  cin >> n;
  int myh, mya, myd, mys;
  cin >> myh >> mya >> myd >> mys;
  VI h(n), t(n), d(n);
  int ret = 0;
  bool able = true;
  REP(i, n) {
    int a, dd, s;
    cin >> h[i] >> a >> dd >> s;
    d[i] = max(0LL, a - myd);
    int tmp = max(0LL, mya - dd);
    if(tmp == 0 && d[i] > 0) {
      able = false;
    } else if(tmp == 0) {
      t[i] = 0;
    } else {
      t[i] = ceil(h[i], tmp);
    }
    if(s > mys) ret += d[i];
  }

  if(!able || ret >= myh) {
    cout << -1 << endl;
    return 0;
  }

  vector<pair<double, int>> idx(n);
  REP(i, n) {
    if(d[i] == 0) {
      idx[i] = {INF, i};
    } else {
      idx[i] = {(double)t[i]/d[i], i};
    }
  }
  sort(ALL(idx));
  // cout << idx << endl;

  int turn = 0;
  REP(i, n) {
    int j = idx[i].second;
    if(t[j] == 0) continue;
    // cout << i << " " << j << " " << ret << " " << turn << endl;
    ret += (turn + t[j] - 1) * d[j];
    turn += t[j];
    if(ret >= myh) {
      cout << -1 << endl;
      return 0;
    }
  }

  if(ret >= myh) cout << -1 << endl;
  else cout << ret << endl;

  return 0;
}