WARush

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

SRM582 Div2 Medium "SpaceWarDiv2"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12605

魔法少女はマジカルパワーを生まれ持った女の子である。地球を守るため、彼女たちは今日も戦う。宇宙からの敵は今まさに地球を侵略しようとしており、魔法少女たちはそれに立ち向かっている。

あなたは魔法少女のステータスであるint magicalGirlStrengthが与えられる。magicalGirlStrength[i]はi番目の少女の強さを表す。あなたは敵のステータスをであるint enemyStrengthとint[] enemyCountが与えられる。enemyStrenth[i]の強さを持った敵が、enemyCount[i]だけ出現している事を表す。

各魔法少女は常に1対1で敵と戦っている。魔法少女は敵の強さ以上の強さを持っている場合、その敵に打ち勝つ事が出来る。

戦いが始まるとき、彼女らの疲労度は0である。彼女らは敵を倒すたびに、疲労度が1増加してしまう。

魔法少女たちの目標は全ての敵を倒す事である。それは、各敵は誰か1人の魔法少女によって打ち負かされなければならない。さらに、魔法少女たちは、戦いが終わった後の、最大の疲労度を最小化したい。

全ての敵を倒す事が出来なければ-1を返せ。そうでなければ、最小化した最大の疲労度を返せ。

制約

1 <= 魔法少女の数 <= 50
1 <= 魔法少女の強さ <= 100
1 <= 敵の強さの種類 <= 50
1 <= 敵の強さ <= 100
1 <= 敵の各強さのその出現数 <= 100



考えた事

最大の疲労度がFであったということは、各魔法少女をF回ずつ戦わせたら全ての敵を倒せたということである。よって、Fについて総当りで試してみればよい。

一番良い戦法は、強い魔法少女を強い敵から戦わせる事である。そこで、Sample1であれば、以下のように試せばよい。

F = 6 NG!
魔法少女 = { 5, 5, 5, 5, 5, 5, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 }
敵       = { 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1}
                                                 ↑
                                                 ココで無理!

F = 7 OK!
魔法少女 = { 5, 5, 5, 5, 5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2 }
敵       = { 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1}

ソースコード

class SpaceWarDiv2 {
public:
    int minimalFatigue(vector <int> magicalGirlStrength, vector <int> enemyStrength, vector <int> enemyCount){
        int N = magicalGirlStrength.size();
        vector<int> enemys;
        for( int i = 0; i < enemyStrength.size(); i++ ){
            int strength = enemyStrength[i];
            for( int j = 0; j < enemyCount[i]; j++ ){
                enemys.push_back( strength );
            }
        }

        // ソートする
        sort( magicalGirlStrength.begin(), magicalGirlStrength.end(), greater<int>() );
        sort( enemys.begin(), enemys.end(), greater<int>() );
        int M = enemys.size();


        // 1人あたりmでいけないかなぁ
        for( int m = M / N + (M % N ? 1 : 0); m <= M; m++ ){
            bool ok = true;
            for( int n = 0; n < N; n++ ){
                for( int i = 0; i < m; i++ ){
                    int id = n * m + i;
                    if( M <= id ) continue;
                    if( magicalGirlStrength[n] < enemys[id] ) ok = false;
                }
            }

            // いけた!
            if( ok ) return m;
        }

        // いけなかった・・・
        return -1;

    }
};