こういう実装は軽いけどちょっと迷う問題はいいね。
https://www.hackerrank.com/contests/unkoder-06/challenges/impossible-game
問題
プレイヤーの初期レベルはXである。
N匹のモンスターがおり、各レベルはA[i]である。
プレイヤーは自分のレベル以下のモンスターを倒すことができ、その際自分のレベルに倒したモンスターのレベル分が加算される。
ここで、プレイヤーがどの順でモンスターを倒しても、全部のモンスターを倒せないよう、いくつかのモンスターを取り除きたい。
最小で何体取り除けばよいか。
解法
先にAを昇順ソートしておく。
プレイヤーは当然レベルの低い順にモンスターを倒すのが良い。
プレイヤーがあるモンスターA[x]を倒せないようにするには、A[0]~A[x-1](のうち取り除かないもの)を全部倒した場合でもプレイヤーのレベルがA[x]に到達しないようにすればよい。
高いレベルのモンスター程倒すとプレイヤーのレベルが大きく上がってしまうので、効率よくプレイヤーのレベルを下げるには高いレベルのモンスターから取り除いていく。
A[x-1]、A[x-2]、…と順に取り除いていき、X + sum(A[0]~A[x-i]) < A[x]となるようなiを見つけたとする。
するとA[x-i+1]~A[x-1]の(i-1)匹が取り除く候補である。
xを総当たりしながら取り除くモンスターの数の最小値を求めれば答え。
int N; ll X,A[55]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>X; FOR(i,N) cin>>A[i]; sort(A,A+N); if(A[N-1]<=X) return _P("-1\n"); int mi=1010; FOR(x,N) { ll tot=X; if(A[x]<=X) continue; FOR(i,x) tot+=A[i]; i=x; while(i>0 && tot >= A[x]) tot-=A[--i]; mi=min(mi,(int)(x-i)); } cout<<mi<<endl; }
まとめ
シンプルで良い問題。
この制限ならO(N^3)かと思ったらO(N^2)なのね。