kmjp's blog

競技プログラミング参加記です

UnKoder #06 : Impossible Game

こういう実装は軽いけどちょっと迷う問題はいいね。
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)なのね。