本番: SRM582 Div1Easy "SpaceWarDiv1"

■時間

30分ぐらい？

■問題 SRM582 Div1 Easy "SpaceWarDiv1"

いろんな強さのモンスターがいて、モンスターを倒せる戦士がN人いる。戦士は自分以下の強さのモンスターは倒せるが、モンスターを倒すたびに「疲労度」が１点増える。モンスターを全員倒したときに一番疲労している戦士の疲労度が最小となるように倒していった場合、この疲労度の最小値はなにか。

■試した解き方

ちゃんと証明してない（ので今はあまり説明できない。あとでちゃんと埋める。）が、greedyで解ける：

戦士を弱い順にみていった時に、

今見ている戦士iの倒すべきモンスターは、残っているモンスターの総数をT、残った戦士の数をNとした場合、最大でもceil(T/N)。

　→それ以上倒しても、戦士iが倒せるモンスターは必ずiより強い戦士も倒せるので意味がない。

なので、

・戦士を弱い順にソート

・最大でceil(T/N)だけ自分以下の強さのモンスターを倒していく

・モンスターが残った場合は-1返す

（もしくは）一番多く倒した戦士の数を返す

public long minimalFatigue(int[] magicalGirlStrength, int[] enemyStrength, long[] enemyCount) {

Arrays.sort(magicalGirlStrength);

long numEnemyLeft=0;

for(long c:enemyCount)

numEnemyLeft+=c;

long max=0;

for(int girl=0;girl<magicalGirlStrength.length;girl++){

long norm=(long)Math.ceil(numEnemyLeft/(magicalGirlStrength.length-girl));

long tot=0;

for(int ei=0;ei<enemyCount.length;ei++){

if(enemyCount[ei]>0 && enemyStrength[ei]<=magicalGirlStrength[girl]){

long numDefeat=Math.min(norm, enemyCount[ei]);

tot+=numDefeat;

enemyCount[ei]-=numDefeat;

numEnemyLeft-=numDefeat;

norm-=numDefeat;

}

}

max=Math.max(max,tot);

}

if(numEnemyLeft>0)

return -1;

return max;

}

■結果

他の人と違う解き方をしていたせいでやたら狙われたが、無事System Test通った。

レーティング： 1221→1341（+120）
４回ぶりにレーティング上がった！

■Editorial
まだ載ってない。

■反省

・他の人は大体binary searchで最大値探してた。自分の方法はO(nt）で解けるので優秀だと思う。

・greedyの解法見つけたのはよかった。感覚的に証明出来る気がしたのでGOしたが、本来危険。