All Green [ AtCoder Beginner Contest 104 C ]

atcoder.jp

問題

問題 i は、解いたときに貰えるスコアが 100*i 点、問題数が p[i] 問、全ての問題を解いたときに貰えるボーナススコアが c[i] である。これらの問題を解いてスコア G以上 を得るとき、少なくとも何問の問題を解かなければならないか。

考察

難しい問題ほど解くのに時間がかかる……といった制約も存在しないので、一見、貰えるスコアが多い順に問題を解いたほうがいいように思えます。しかし、以下のようなケースが存在します。

2 1000
1 99999
10 100

100点問題が1問と、200点問題が10問あり、1000点以上を得ることが目標です。

200点問題を5問解くと合計が1000点になりますが、100点問題は1問解くだけで全完ボーナス99999点が貰えるので、100点問題を1問だけ解くのが最適となります。

全完ボーナスの存在がなければスコアの大きい順に貪欲に解いていく方法で解けますが、全完ボーナスが存在するために問題が複雑になっています。

そこで、それぞれの問題について

・全完ボーナスが貰えるまで解く（全ての問題を解く）
・一問も解かない

の2通りの解き方をビット全探索で全探索します。問題数は 1<=D<=10 なので間に合います。

もし、ある組み合わせにおいて、いくつかの問題を全完ボーナスが得られるまで解いたにもかかわらず、それでもまだ目標のスコアに届かない場合は、スコアが最も多い問題を全完しないギリギリまで（p[i]-1問まで）解きます。

それでもまだ届かない場合は、もともと最適な選び方ではなかったということで、その組み合わせを放棄します。

コード

void solve (FastScanner in, PrintWriter out) {
	
	//入力
	int n = in.nextInt(), goal = in.nextInt();
	Problem[] p = new Problem[n];
	for (int i=0; i<n; i++) {
		p[i] = new Problem(in.nextLong(), (i+1)*100, in.nextLong());
	}
	
	//ビット全探索+@
	long min = Long.MAX_VALUE;
	for (int i=0; i<(1<<n); i++) {

		int num = 0; //その組み合わせでは何問解いたか？
		long sum = 0L; //その組み合わせで得られたスコアの合計
		
		//全完していない問題のうち、最もスコアが高いもの、すなわち
		//i をビット表現したときに最も右側にある 0 の位置を記録する変数
		int rightMost = -1; 

		for (int j=n-1; j>=0; j--) { //
			if ((1&i>>j) == 1) {
				sum += p[j].num * p[j].score + p[j].bonus;
				num += p[j].num;
			}
			else if ((1&i>>j) == 0 && rightMost == -1) {
				rightMost = j;
			}
		}
		
		//sum が目標スコア以上の場合は、解いた問題の数をそのまま min に記録する
		if (sum >= goal) {
			min = Math.min(min, num);
			continue;
		}
		else if (rightMost != -1){
			//そうでない場合かつ、全完していない問題が少なくとも1つある場合
			
			//目標スコアに届くまで、スコアが最も多い問題を needNum 回解く必要がある
			long needNum = (goal-sum+p[rightMost].score-1) / p[rightMost].score;
			
			if (needNum > p[rightMost].num) {
				//スコアが最も多い問題が needNum 問より少ないなら、放棄
				continue;
			}
			else {
				//そうでないなら、スコアが最も多い問題を needNum 問解き、
				//min を更新する
				min = Math.min(min, num + needNum);
			}
		}
		
	}

	out.println(min);

}

static class Problem {
	long num, score, bonus;
	Problem (long a, long b, long c) {
		num = a; score = b; bonus = c;
	}
}