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