Codeforces #190 Div1. B. Ciel and Duel

カードゲームを題材にした問題。
http://codeforces.com/contest/321/problem/B

問題

自分はそれぞれ1～8000の強さを持つM枚の手札を持つ。
相手は、同じく1～8000の強さを持つN枚の手札を持つ。相手の手札は、攻撃と防御のどちらかの状態である。

自分は以下の手順をとることができる。

• 相手の手札が0枚なら、自分の手札を1枚消費し、強さの分ダメージを与える。
• 自分の手札が相手の攻撃状態の手札以上の強さを持つなら、両者の手札を消し、強さの差分分ダメージを与える。
• 自分の手札が相手の防御状態の手札より大きな強さを持つなら、両者の手札を消して終了。

相手に与えられる最大ダメージを答えよ。

解法

自分の作戦として、2つのアプローチがある。

1. 相手の手札を全部消し、後は残りの手札で相手を攻撃する。
2. 相手の手札を全部消すのはあきらめ、弱い攻撃手札に攻撃して差分ダメージを稼ぐ。

守備カードを消すときは、差分がダメージにならないので強すぎるカードを出す必要はない。

よって、前者のアプローチでは、相手の守備カードをできるだけ近い強さのカードで消し、その後攻撃カードに対し自分の強いカードを順に当てて消せばよい。

後者のアプローチでは、守備カードを消すことはあきらめ、敵の攻撃カードの下位X枚と自分のカード上位X枚を当てる、という作戦を各Xについて行えばよい。

両者の最大値が答え。

int N,M;
vector<int> C[2],S;

int alldef() {
	int i,j,k,x,y;
	int used[101];
	int sum=0;
	ZERO(used);
	
	FOR(i,C[1].size()) {
		FOR(j,M) {
			if(used[j]==0 && S[j]>C[1][i]) {
				used[j]=1;
				break;
			}
		}
		if(j==M) return 0;
	}

	FOR(i,C[0].size()) {
		FOR(j,M) {
			if(used[j]==0 && S[j]>=C[0][i]) {
				sum+=S[j]-C[0][i];
				used[j]=1;
				break;
			}
		}
		if(j==M) return 0;
	}
	
	FOR(j,M) if(used[j]==0) sum+=S[j];
	return sum;
}

int subdef() {
	int ma=0;
	int i,j,k,x,y;
	
	for(i=1;i<=min(C[0].size(),S.size());i++) {
		int sum=0;
		FOR(k,i) {
			if(C[0][k]>S[S.size()-i+k]){ sum=-1; break;}
			sum += S[S.size()-i+k]-C[0][k];
		}
		ma=max(ma,sum);
	}
	
	return ma;
	
}

void solve() {
	int f,r,i,j,k,l;
	ll x,y,rx,ry;
	
	cin>>N>>M;
	FOR(i,N) {
		string s;
		cin>>s>>x;
		C[s=="DEF"].push_back(x);
	}
	FOR(i,M) {
		cin>>x;
		S.push_back(x);
	}
	sort(C[0].begin(),C[0].end());
	sort(C[1].begin(),C[1].end());
	sort(S.begin(),S.end());
	_P("%d\n",max(alldef(),subdef()));
}

まとめ

上の解答かいてて思ったけど、もう少し答えはシンプルに書けそうね。