yukicoder No.23 技の選択

問題

No.23 技の選択 - yukicoder
体力がの敵を

1. 攻撃力の通常攻撃（必ず当たる）
2. 攻撃力の必殺技（2/3の確率で当たる）

の二つの攻撃を使って倒したい．最小の攻撃回数の期待値はいくつか．

解法

解説を見たら全部DPで解いていたが，通常攻撃の使う回数でループを回しても解ける．
必殺技は2/3の確率で当たるので，必殺技が全部当たって倒す回数の3/2が必殺技で倒せる回数の期待値である．通常攻撃を回使った時の，必殺技を使う回数の期待値は

となる．

ソースコード

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP (i,0,(int)(n)-1)
#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP (i,(int)(n)-1,0)
#define INF (int)1e8
#define MOD (int)(1e9+7)

typedef long long ll;

int main(void) {
    int i, h, a, d;
    double ans = 1e5;
    cin >> h >> a >> d;
    rep (i,(h+a-1)/a+1)
        ans = min(ans,i+(max(0,h-a*i)+d-1)/d*1.5);
    cout << ans << endl;
    return 0;
}