公式
E - Critical Hit 解説 by nok0
シンプルな動的計画法による解答\(\mathrm{dp}[i]\) を、モンスターの体力が \(i\) である状態からモンスターの体力が \(0\) 以下になるまでにかかる攻撃回数の期待値と定義します。
答えは \(\mathrm{dp}[N]\) です。この動的計画法は、最初の攻撃で与えるダメージに着目して場合分けすることで、昇順に埋めることが可能です。計算量は \(\mathrm{O}(N)\) です。
また、この動的計画法は \(i\geq 2 \) のときに遷移が \(i\) に依らないことに着目すると行列累乗で高速化可能で、\(\mathrm{O}(\log N)\) 解法が得られます。
線形時間解法の実装例(c++):
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;
int main() {
int n, p;
cin >> n >> p;
vector dp(n + 1, mint(0));
mint critical = mint(p) / 100, normal = 1 - critical;
for(int i = 1; i <= n; i++)
dp[i] = (dp[max(0, i - 2)] * critical + dp[i - 1] * normal) + 1;
cout << dp.back().val() << endl;
}
対数時間解法の実装例(c++):
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;
template <class T>
struct matrix {
int h, w;
vector<vector<T>> e;
matrix(int h_, int w_) : h(h_), w(w_), e(h_, vector<T>(w_)) {}
std::vector<T> &operator[](int p) {
return e[p];
}
const std::vector<T> &operator[](int p) const {
return e[p];
}
matrix operator*(const matrix &m) {
assert(w == m.h);
matrix ret(h, m.w);
for(int i = 0; i < h; i++) {
for(int j = 0; j < m.w; j++) {
for(int k = 0; k < w; k++) {
ret[i][j] += e[i][k] * m[k][j];
}
}
}
return ret;
}
matrix operator^(long long p) const {
assert(h == w);
matrix I(h, w), b(*this);
for(int i = 0; i < h; i++) I[i][i] = T(1);
while(p) {
if(p & 1) I = I * b;
b = b * b;
p >>= 1;
}
return I;
}
};
int main() {
int n, p;
cin >> n >> p;
mint critical = mint(p) / 100, normal = 1 - critical;
matrix<mint> r(3, 1);
r[0][0] = 1 + normal;
r[1][0] = 1;
r[2][0] = 1;
matrix<mint> m(3, 3);
m[0] = {normal, critical, 1};
m[1] = {1, 0, 0};
m[2] = {0, 0, 1};
r = (m ^ (n - 1)) * r;
cout << r[1][0].val() << endl;
}
投稿日時:
最終更新: