yukicoder No.23 技の選択

解説を読んでもみんなDPって言ってるんだけど……

必殺技が当たるまでの回数の期待値は1.5回なので、初めから「コスト1.5で命中100%」と考えて良い
よって攻撃を繰り出す順序は関係なく「通常攻撃をi回行って、HPが残っていれば必殺技で削る」という戦略での期待値を求めれば良い

int main(){
	int H,A,D,i,h;
	double m,t;
	scanf("%d%d%d",&H,&A,&D);
	m=H;
	//自明な上界。通常攻撃で1以上のダメージを与えるのでH回殴れば確実に倒せる
	for(i=0;i*A<H+A;i++){
		h=H;
		t=i;h-=i*A;
		//通常攻撃をi回
		if(h>0)t+=(h+D-1)/D*1.5;
		//残っていれば必殺技
		if(t<m)m=t;
	}
	printf("%f",m);
	return 0;
}

doubleを扱うのは面倒なので全体を2倍して出力の時に2で割る
ループの終了条件も、HをAずつ減らしていって-A以下になれば終わり、として良い
mの初期化も省略

H,A,D,i,m;
main(t){
	scanf("%d%d%d",&H,&A,&D);
	for(;H>-A;H-=A){
		t=(H+D-1)/D*3*(H>0)+i++*2;
		m=m&&m<t?m:t;
	}
	i=!printf("%f",m/2.);
}

いつもの

H,A,D,i,m;
main(t){
	for(scanf("%d%d%d",&H,&A,&D);H>-A;m=m&&m<t?m:t,H-=A)t=(H+D-1)/D*3*(H>0)+i++*2;
	i=!printf("%f",m/2.);
}

補足：
確率pが起こるまでの試行回数の期待値が1/pであることの証明
求める期待値をxとする（x<∞を仮定する）
1回目の試行で外れた場合、2回目以降で起こるまでの回数の期待値はxなので
x=1+(1-p)*x
方程式を解いてx=1/p

メモ

yukicoderでゆるふわgolf

yukicoder No.23 技の選択