パンプキン #C++

パンプキン

考察

召喚と抽出の2つの操作があって、どうすればいいのかよくわからない
なので、最初に全てのカードを抽出した状態にする。すると、あとは召喚するかしないかだけを考えれば良くなる。
最初に全てのカードを抽出した状態にするので、初期状態のマナは$\sum_{i=0}^{N-1}Gi$となる。
カードを走査する。そのカードを抽出に使用する場合は何もしない（初期状態で全てのカードを抽出用として使ったので）。
そのカードを召喚に使用する場合、マナを$Ci$消費するので初期のマナから$Ci$が引かれる。さらに、抽出するはずだったマナを$Gi$を取り消すことになるので、初期のマナから$Gi$が引かれる。
つまり、カード$i$を召喚するとマナは$-(Ci+Gi)$されることになる。
よってこのゲームは、「初期状態のマナが$\sum_{i=0}^{N-1}Gi$。カードを召喚すると$-(Ci+Gi)$される。このとき、召喚できるカードは何枚か？」というゲームに落とし込むことができる。
召喚すると減るマナ$Ci+Gi$は小さいほうが良い。よって、$Ci+Gi$が小さい方からカードを召喚するのが最善手であることがわかる。

解法

初期状態のマナを$\sum_{i=0}^{N-1}Gi$とする。
$Ci+Gi$の配列を作り、昇順にソートする
[0, N)の区間を捜査し、$Ci+Gi$が小さいものから召喚していく

コード

インデックスの情報を使うかもしれないから{Ci+Gi, i}の配列にしたけど、結局インデックス使わなかったから普通の配列でもよかった

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

#define int long long

using p = pair<int, int>;

int N;
vector<int> C, G;
vector<p> A; // A[i]: {Ci+Gi, i}

signed main() {
  cin >> N;
  C.resize(N);
  G.resize(N);
  A.resize(N);

  int mana = 0;
  for (int i = 0; i < N; i++) {
    cin >> C[i] >> G[i];
    mana += G[i];
    A[i] = {C[i]+G[i], i};
  }
  sort(A.begin(), A.end());

  // ここから先がゲームしてる部分
  int ans = 0;
  for (int i = 0; i < N; i++) {
    if (A[i].first <= mana) {
      ans++;
      mana -= A[i].first;
    }
  }

  cout << ans << endl;

  return 0;
}

要点

初期状態を、全てのアイテムを取った状態とする。そして全て取ったアイテムのうち、どれを取り去るのかを考える
- この考え方典型っぽい
- そうすることで、考えることが減って簡単な問題に落とし込むことができる。

感想

典型知ってないと初見で解くのはきつそう。
ミドリムシくん、TABくんありがとう。
かぼちゃおいちい〜って助言、すごく役に立ちました。こうきさんありがとうございました。