読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

Coder-Strike 2014 Round2 - C. Jeopardy!

体調不良ながらCoder-Strike Round2に参加。
そこそこの速度で全完できたと思っていたらDがしょうもないミス、Eが色々小ミスがあってそこそこの順位に。
Eはかなりミスが積もってたのでしょうがないとして、DはFirst Answerのチャンスを逃したのが残念。
http://codeforces.com/contest/413/problem/C

問題

N問の問題があり、それぞれ正解するとA[i]のお金がもらえる。
このうちM問が指定されており、それらはオークション問題である。

通常の問題は正解するとA[i]だけ賞金を貰える。
オークション問題は、自分の持ち金分まで貰える金額を吊り上げられる。

任意の順で解答可能とするとき、もらえる最大金額を答えよ。

解法

オークション問題は自分の持ち金分まで賞金を増やせるので、金額が多い状態で挑むのが良い。
よって、まず通常問題を正解して持ち金を溜める。

そしてオークション問題を金額の多い順に解けばよい。
最初のオークション問題で、持ち金が賞金より多ければ持ち金を倍にできるし、賞金の方が多ければその分持ち金を増やせる。
2問目以降のオークション問題は確実に持ち金が賞金を上回るので、毎問持ち金を倍に出来る。

int N,M;
ll A[101];
int B[101];

void solve() {
	int f,i,j,k,l,x,y;
	vector<ll> AA,BB;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	FOR(i,M) cin>>x, B[x-1]=1;
	ll cur=0;
	FOR(i,N) {
		if(B[i]) BB.push_back(A[i]);
		else cur+=A[i];
	}
	sort(BB.begin(),BB.end());
	reverse(BB.begin(),BB.end());
	
	FOR(i,BB.size()) cur+=max(BB[i],cur);
	
	cout << cur << endl;
	
}

まとめ

解き方はともかく、問題文がだいぶわかりにくい。

広告を非表示にする