WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
}