AOJ 2826 - ゲームバランス - ツバサの備忘録

解法

倒すまでに最小 $M$ 回以上かかるなかで最大となる $X$ を二分探索で求めます。
ゲームクリアできない場合、 $1 + X \leqq s_{1}$ になります。二分探索時は、ゲームクリアまでに $M$ 回以上かかっている、と仮定します(最後に求まった $X$ を確認した場合にゲームクリアできなかった場合は答えが-1になります)。
以降は、ゲームクリアができると仮定して話を進めます。
そして、そもそも、 $X=1$ の場合に戦闘が $M$ 回未満になる場合は-1になります。これを排除しておきます。
$X$ を固定した際に、何回かかるかを調べます。
現在のレベルを $l$ とします、初期値は1です。
ここから、レベルが $l$ の際に一番レベルが上がる敵を毎回倒すことをシミュレートします。 $M$ 回を超えたらそれ以上シミュレートする必要がないので、そこで打ち切ります。 $s_{N}$ を倒せるレベルになっていたら、その場合もシミュレートを終了します。
レベルが一番上がるのは、 $l$ との差が最も小さい強さを持つ敵です。
そこで、強さ $l$ 以上を持つ敵の中で一番弱い敵を二分探索で調べます。
そして、その敵が倒せるかどうかを判定します。
倒せる場合はその際に上がるレベルをメモします。
次に、先ほど調べた敵の1つ手前にいる敵について、上がるレベルをメモします。この際は、自分のレベルが $l$ のため確実に倒せることから、倒せるかどうかの判定をする必要はありません。
そして、今調べた2体のうち、よりレベルが上がる方を選択して倒します。
これを繰り返します。