読者です 読者をやめる 読者になる 読者になる

SRM 582 Div2 Medium SpaceWarDiv2

問題

SRM582は解説記事がないようだ.

魔法少女と敵が戦う.魔法少女と敵はそれぞれ強さがあって,敵の強さが魔法少女と同等あるいはそれよりも小さい場合,敵を倒せる.敵を倒す度に疲労度1がたまる. 各魔法少女の疲労度の最大が最小化した時の疲労度を答える問題.

解答

  • 疲労度が固定されれば,それを成り立たせるような選択方法は強い魔法少女から順に強い敵にぶつける方法.
  • 入力はそれほど大きくないので疲労度の小さい方から順にシミュレーションしていって,成り立つかどうかを検証していく.
class SpaceWarDiv2
{
public:
  int minimalFatigue(vector <int> magicalGirlStrength, vector <int> enemyStrength, vector <int> enemyCount)
    {
      int i, j;
      int n = magicalGirlStrength.size();
      int m = enemyStrength.size();
      sort(magicalGirlStrength.begin(), magicalGirlStrength.end());
      vector<pair<int, int> > enemy(m);
      int upper_res = 0;
      for(i = 0; i < m; i++){
        enemy[i] = pair<int, int>(enemyStrength[i], enemyCount[i]);
        upper_res += enemyCount[i];
      }
      sort(enemy.begin(), enemy.end());
      if (enemy[m-1].first > magicalGirlStrength[n-1]) return -1;
      for(i = 1; i < upper_res+1; i++){
        vector<pair<int, int> > enemy2 = enemy;
        int cur = n-1;
        int cur_f = i;
        j = m-1;
        // cout << endl << "**** upper = " << i << endl;
        while (j >= 0 && cur >= 0){
          // cout << "cur=" << cur << " cur_f=" << cur_f << endl;
          if (enemy2[j].first <= magicalGirlStrength[cur]){
            if (enemy2[j].second <= cur_f){
              cur_f -= enemy2[j].second;
              enemy2[j].second = 0;
              j--;
            }else{
              enemy2[j].second -= cur_f;
              cur_f = 0;
            }
            if (cur_f == 0) {
              cur--;
              cur_f = i;
            }
          }else{
            break;
          }
        }
        if (j < 0) return i;
      }
      return -1;
    }
};