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

解いた問題のソースコードと解説など。


SRM 582 Div1 Easy SpaceWarDiv1

問題

魔法少女たちがおり、彼女らの力がvector int で与えられる。敵が複数おり、強さenemyStrength[i]の敵がenemyCount[i]匹いる。魔法少女達は自分と同じか自分より弱い敵を倒すことができ、一体倒すにつき疲労度が+1される。敵をすべて倒した時にもっとも疲労度の高い魔女の疲労度をFとする。Fを最小化せよ。

やりかた

二分探索でいける。Fを固定した時に、そのFの疲労度のうちで敵を倒せるかどうか判定して、倒せるようならもうすこしFを小さくしてみて、倒しきれないようならFをもう少し大きくしてみる。これをくりかえす。判定の仕方としては少女[i]が倒せる敵の数をFを上限にして倒す。これをすべての少女について行なってみて、その時のFで敵を残らず倒せるかどうか調べればいい。

class SpaceWarDiv1 {
public:
  long long minimalFatigue(vector <int> magicalGirlStrength, vector <int> enemyStrength, vector<long long> enemyCount) {
    int N = magicalGirlStrength.size();
    int M =  enemyStrength.size();

    vector<pair<ll, ll> > sc;
    for(int i = 0; i < M; i++)
      sc.push_back(make_pair(enemyStrength[i], enemyCount[i]));

    sort(ALL(magicalGirlStrength));
    sort(ALL(sc));

    ll lb = 1, ub = (ll)1e18;
    while(ub != lb){
      ll mid = (lb + ub) / 2;
      vector<ll> rem;
      for(int i = 0; i < M; i++) rem.push_back(sc[i].second);

      for(int i = 0; i < N; i++){
	ll tmp = mid;
	for(int j = 0; j < M; j++){
	  if(sc[j].first <= magicalGirlStrength[i]){
	    ll kill = min(tmp, rem[j]);
	    rem[j] -= kill;
	    tmp -= kill;
	  }
	}
      }
      
      if(count(ALL(rem), 0) == M) ub = mid;
      else lb = mid + 1;
    }
    return lb == (ll)1e18 ? -1 : lb;
  }
};

出場できなかったので練習。
最初、

ll kill = min(tmp, rem[j]);
rem[j] -= kill;
tmp -= kill;

rem[j] -= min(tmp, rem[j]);
tmp -= min(tmp, rem[j]);

として、一時退避をおこなっていなかったため、どうしても答えが合わなかった。

しょげないでよBaby 眠れば治る