TopCoderOpen 2017 Regional Wildcard : Easy ArmorUp

Mediumをしょうもないミスで1WAしたので、出なくてよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=14696

問題

あるRPGにおける戦闘を考える。
敵の最大HPがM、現在のHPがCとする。

攻撃力Dで敵に攻撃したとき、敵の防御力をaとするとDからa%引いた分だけ相手のHPが減少する。
HPが0以下になるとその時点で敵は死亡する。
敵の防御力は現在HPと最大HPの比率で定まり、現在HPが最大HPに対し2%低い毎に1上昇する。
各数値は実数値を取りうる。

ここでK回の攻撃で敵が死亡するような最小の攻撃力Dを求めよ。

解法

複数解法がある。

1つは、Dを二分探索で求める。
1回攻撃後の敵のHPはCからC-D*(1-C/2M)に減少するので、これを漸化式とみなし行列累乗を用いれば、Dに対しK回攻撃後の敵の残HPが高速に求められる。
ただし注意点として、敵のHPが-M以下だと次の攻撃時回復してしまい妙なことになるので、明らかに途中で相手のHPが0を切る場合、途中で処理を打ち切る。

もう1つはもっと簡単な数式に落とす方法。
まず敵のHPをMだけ底上げし、最大HPが2M、初期HPが(M+C)で、HPがM以下になったら死亡、と考える。
さら全体をMで割り、最大HPが2、初期HPがC'=(M+C)/Mで、HPが1以下になったら死亡、としよう。
この問題に対する解をM倍すれば元の解になる。

1回攻撃後の敵のHPは、C'-D(C'/2)=C'(1-D/2)となる。
K回攻撃してちょうどHPが1になるのは、C'(1-D/2)^k=1より(1-D/2)=C'^(-1/k)なので、簡単な累乗でDが求められる。

class ArmorUp {
	public:
	double minimalDamage(int maxHP, int currentHP, int k) {
		double a=1.0*currentHP/maxHP;
		double b=1/(1+a);
		double c=pow(b,1.0/k);
		double d=1-c;
		
		return d*maxHP*2;
	}
}

まとめ

後者を本番で自身持って出せる気がしない。