Edited at

パンプキン


考察


  • 召喚と抽出の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$が小さい方からカードを召喚するのが最善手であることがわかる。


解法


  1. 初期状態のマナを$\sum_{i=0}^{N-1}Gi$とする。

  2. $Ci+Gi$の配列を作り、昇順にソートする

  3. [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くんありがとう。

  • かぼちゃおいちい〜:heart:って助言、すごく役に立ちました。こうきさんありがとうございました。