5完2WA。

競プロフレンズさんならきっと、教育的で面白い典型問題（かつ、テーマあり）で揃えてくれると予想してました
予想通り面白い問題ばかりだったです
ありがとうございました！
— Toy (@mdstoy) 2020年1月26日

面白かったです！

各問題

A - Serval vs Monster

これは、切り上げ除算の答えが回数ですので、それを計算してください。

「同じ必殺技を2度以上使うことなく」ということは、「すべての必殺技を1度ずつ使える」ということなので、すべての必殺技のダメージを加算してモンスターの体力以上なら勝ち、下回れば負けということになります。

普通の攻撃は一律1のダメージしか与えられませんが、必殺技はいくら体力のあるモンスターでも必殺なので、必殺技を体力の多いモンスターに使うのが最適です。

なので、モンスターを体力の降順にソートして、上位K体のモンスターは必殺技で倒し、残りN-K体のモンスターは攻撃を繰り返して倒せばよいです。

通常攻撃の回数は必殺技を使わなかったN-K体のモンスターそれぞれに対して体力分が必要ですから、N-K体のモンスターの体力を足せばよいです。

攻撃によってモンスターは、倍々で増えていきます。最初の体力が10なら、攻撃→5が2体、それぞれを攻撃→2が4体という具合です。

要するに攻撃回数は、モンスターの体力が1->0になるまでの間で、1 + 2 + 4 + 8 + ....と加算されていきます。

えー、個数無制限のナップサック問題です。以上。

なのに時間ギリギリまでAC取れなかった水色コーダーがここに・・・。DP練習不足・・・。

端から倒していくのが最適なのは、それはそうで、愚直にやると間に合わないので、何かしないといけないのですが、私はEを最後まで考えていたので、こちらに手が回りませんでした・・・。ああ・・・。

いや、ほんまに典型のナップサックがさくっとできないのはまずいですね・・・。DPのトレーニングが必要ですね。

f:id:mdstoy:20200126230626p:plain