Official

B - スキルアップの階段 / Stairway to Skill Up Editorial by kyopro_friends


解く問題の集合が同じであれば、解く順序によらず最終的なスキルレベルは同じになります。また、問題を解くことでスキルレベルは増加していくので、ある時点で解ける問題がそれ以降に解けなくなることはありません。このことから、どの時点においても、解ける問題があればその問題を解いてよいです。

まだ解いてない問題のうち難易度が最も低い問題に注目します。この問題を解くことができない場合、どの問題も解くことができません。解ける場合、この問題を解くとしてよいです。

よって、全ての問題を難易度の低い順に解けるだけ解くのが最適です。

実装例 (C++)

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

int main(){
  int n;
  long long s, t;
  cin >> n >> s >> t;
  vector<int>d(n);
  for(int i=0; i<n; i++) cin >> d[i];
  sort(d.begin(), d.end());
  
  for(int i=0; i<n; i++){
    if(d[i] <= s){
      s += d[i];
    }
  }
  
  if(s >= t){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

実装例 (Python)

N, S, T = map(int, input().split())
D = list(map(int, input().split()))
D.sort()
for d in D:
  if d <= S:
    S += d

if S >= T:
  print("Yes")
else:
  print("No")

posted:
last update: