カードゲームを題材にした問題。
http://codeforces.com/contest/321/problem/B
問題
自分はそれぞれ1~8000の強さを持つM枚の手札を持つ。
相手は、同じく1~8000の強さを持つN枚の手札を持つ。相手の手札は、攻撃と防御のどちらかの状態である。
自分は以下の手順をとることができる。
- 相手の手札が0枚なら、自分の手札を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())); }
まとめ
上の解答かいてて思ったけど、もう少し答えはシンプルに書けそうね。