Codeforces #190 Div2 D "Ciel and Duel"
問題
http://codeforces.com/contest/322/problem/D
訳
キツネのシエルは友達のジローとカードゲームで遊んでいる。
ジローはn枚のカードを持っており、それぞれのカードはポジション(アタック、ディフェンス)と強さという2つの属性が設定されている。シエルはm舞のカードを持っており、こちらも同じ2つの属性を持っている。シエルのカードのポジションは全てアタックである。
現在シエルのターンであり、シエルは下記のような操作を繰り返し行う事が出来る。
1. カードXを選ぶ。ただし、以前に選んだカードは使えない。 2. もしジローに生き残ったカードが無ければ、彼はXの強さ分だけダメージを受ける そうでなければ、シエルはジローの生き残っている下記のようなカードYを選ぶ。 3. もしYのポジションがアタックならば、Xの強さ>=Yの強さでなくてはならない。 そして、カードYは死に、ジローはXの強さ-Yの強さだけダメージを受ける 4. もしYのポジションがディフェンスならば、Xの強さ>Yの強さでなくてはならない。 そして、カードYは死ぬが、ジローはダメージを受けない
シエルは好きなときに自分のターンを終わらす事が出来る(なので一枚も選ばなくてもよい)。ジローに与えるダメージを最大化せよ。
制約
1 <= n, m <= 100
1 <= 各カードの強さ <= 8000
考えた事
制約からいってなんかDPっぽいが、そうでもない。(DPでいけるかもだけど)アタックなカードだけに集中攻撃するか、カードを全滅させ無防備にするか、の2つの場合分けで考える。
アタックなカードを集中攻撃する場合、シエルの強いカードを使って、ジローの弱いカードを狙っていく戦法をとる。それを何枚でやるか総当りすればよい。
カードの全滅を狙う場合、とりあえずディフェンスなカードを最低限のカードを使って全滅させる。それに成功したら、アタックなカードを好きなように全滅させる。それに成功したら無防備なジローを狙う。
ソースコード
int an, dn, jin, cn; int atk[110]; int dif[110]; int cs[110]; int main() { an = 0, dn = 0; cin >> jin >> cn; for( int i = 0; i < jin; i++ ){ string p; cin >> p; if( p == "ATK" ){ cin >> atk[an++]; }else{ cin >> dif[dn++]; } } for( int i = 0; i < cn; i++ ){ cin >> cs[i]; } sort( atk, atk + an, greater<int>() ); sort( dif, dif + dn, greater<int>() ); sort( cs, cs + cn, greater<int>() ); int ans = 0; // アタックなカードのみ狙う for( int i = 1; i <= min( an, cn ); i++ ){ int res = 0; for( int j = 0; j < i; j++ ){ res += max( cs[j] - atk[j+an-i], 0 ); } ans = max( ans, res ); } // 全滅を狙う bool use[110] = { false }; int cnt = 0; // ディフェンスをやっつける for( int i = dn - 1; i >= 0; i-- ){ for( int j = cn - 1; j >= 0; j-- ){ if( !use[j] && dif[i] < cs[j] ){ cnt++; use[j] = true; break; } } } if( cnt == dn ){ // アタックをやっつける int res = 0; bool ok = true; for( int i = 0; i < an; i++ ){ for( int j = 0; j < cn; j++ ){ if( use[j] ) continue; if( cs[j] < atk[i] ){ ok = false; break; } res += cs[j] - atk[i]; use[j] = true; break; } } // ジローをやっつける if( ok ){ for( int j = 0; j < cn; j++ ){ if( use[j] ) continue; res += cs[j]; } ans = max( ans, res ); } } cout << ans << endl; }