読者です 読者をやめる 読者になる 読者になる

h_nosonの日記

競プロなど

yukicoder No.23 技の選択

yukicoder 期待値

問題

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

  1. 攻撃力Aの通常攻撃(必ず当たる)
  2. 攻撃力Dの必殺技(2/3の確率で当たる)

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

解法

解説を見たら全部DPで解いていたが,通常攻撃の使う回数でループを回しても解ける.
必殺技は2/3の確率で当たるので,必殺技が全部当たって倒す回数の3/2が必殺技で倒せる回数の期待値である.通常攻撃をi回使った時の,必殺技を使う回数の期待値は
(\max(H-A*i,0)+b-1)/b*1.5
となる.

ソースコード

#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;
}