ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

yukicoder No.23 : 技の選択

概要

体力Hの敵にダメージを与えて倒すことを考える。

こちらには2種類の攻撃方法がある。

  • 通常攻撃: 1回の攻撃でAダメージ与える。必中技。
  • 必殺技: 1回の攻撃でDダメージ与える。2/3の確率で命中。1/3の確率で攻撃を外す。

この2種類の攻撃を使って敵を倒すとき、攻撃回数の期待値の最小値を求めよ。

1≦H,A,D≦10000

http://yukicoder.me/problems/33

解法

確率pで当たり、(1-p)で外れとなるとき、当たりが出るまでの試行回数の期待値はp^-1となる。(0<p<1)

これが分かれば、あとは動的計画法で求めることができる。

期待値について

ちなみに上記の期待値については以下のような感じで証明することができる。


{ \displaystyle
当たる確率をp、外れる確率を(1-p)、試行回数の期待値をEとする。\\
E = p + 2p(1-p) + 3p(1-p)^2 + 4p(1-p)^3 + ... + np(1-p)^{n-1}\\
両辺に(1-p)をかけて、\\
(1-p)E = p(1-p) + 2p(1-p)^2 + 3p(1-p)^3 + ... + (n-1)p(1-p)^{n-1} + np(1-p)^n\\
これらをひくと、\\
pE = p + p(1-p) + p(1-p)^2 + p(1-p)^3 + ... + p(1-p)^{n-1} - np(1-p)^n\\
\  \ E = 1 + (1-p) + (1-p)^2 + (1-p)^3 + ... + (1-p)^{n-1} - n(1-p)^n\\
\ \ \ \ = \{\frac{1 - (1-p)^n}{1 - (1-p)} - n(1-p)^n\}\\
\ \ \ \ = \lim_{n \to \infty} \{\frac{1 - (1-p)^n}{p} - n(1-p)^n\}\\
\ \ \ \ = \frac{1}{p}
}


ソースコード

#include <bits/stdc++.h>

#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define F first
#define S second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

int main() {
  // ios_base::sync_with_stdio(false);
  int H, A, D;
  cin >> H >> A >> D;

  const double INF = 1e9;
  vector<double> dp(H + 1, INF);
  dp[0] = 0;

  rep(i, H + 1) {
    if(dp[i] == INF) continue;
    int d1 = min(H, i + A);
    dp[d1] = min(dp[d1], dp[i] + 1);
    int d2 = min(H, i + D);
    dp[d2] = min(dp[d2], dp[i] + 1.5);
  }

  cout << dp[H] << endl;

  return 0;
}