結果
問題 | No.23 技の選択 |
ユーザー | codershifth |
提出日時 | 2015-07-20 22:30:21 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,756 bytes |
コンパイル時間 | 1,319 ms |
コンパイル使用メモリ | 159,200 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-28 16:47:29 |
合計ジャッジ時間 | 2,320 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 1 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 2 ms
5,376 KB |
testcase_24 | AC | 1 ms
5,376 KB |
testcase_25 | AC | 1 ms
5,376 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 2 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | AC | 2 ms
5,376 KB |
testcase_30 | AC | 2 ms
5,376 KB |
testcase_31 | AC | 2 ms
5,376 KB |
testcase_32 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h>typedef long long ll;typedef unsigned long long ull;#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)#define REP(i,n) FOR(i,0,n)#define RANGE(vec) (vec).begin(),(vec).end()using namespace std;class ActionChoice {public:void solve(void) {int H,A,D;cin>>H>>A>>D;//// Exp[h] を h ダメージを与えるときの戦闘回数期待値とする。// 最善の戦略をとるのでそれぞれ期待値を計算して比較することになる//// 確率pで当たり、(1-p)で外れとなるとき、当たりが出るまでの試行回数の期待値はp^-1となる。(0<p<1)// (http://purple-jwl.hatenablog.com/entry/2015/03/23/225839 参照)//// Exp[h] = Exp[h-A] + 1// or// Exp[h] = Exp[h-D] + 1/p//// 必殺技を何回か試して当たらなくて通常攻撃に切り替えるくらいなら最初から// 通常攻撃をするほうが期待値は小さくてすむ。// つまり必殺技を出すなら当たるまでやる。(失敗のコストを払っても削れる D が大きいなら意味がある)//vector<double> exp(H+1,0); // exp[h] := ダメージ h を与えたときの最小戦闘回数期待値FOR(h, 1, H+1){exp[h] = min(exp[max(h-A,0)] + 1, exp[max(h-D,0)] + 1.5);}cout<<exp[H]<<endl;}};#if 1int main(int argc, char *argv[]){ios::sync_with_stdio(false);auto obj = new ActionChoice();obj->solve();delete obj;return 0;}#endif