AtCoder が提供しているABC（AtCoder Beginner Contest）280 のE問題をC++とPythonで解いてみました。ABC280は、2022年12月3日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Critical Hit（Difficulty : 1251）
問題はリンク先をご覧ください。
3項の漸化式で確率を求めるDPです。AtCoder Problems による Difficulty は、1251 でした。
解答案
dp[i] を、モンスターの体力が i である状態からモンスターの体力が 0 以下になるまでにかかる攻撃回数の期待値と定義します。明らかに
dp[0] = 0、dp[1] = 1
となります。漸化式は以下となります。右辺で1を加えているのは、攻撃回数が1増えるためです。
dp[i] = dp[i-2] * p/100 + dp[i-1] * (1 ー p/100) + 1 (i $\geqq$ 2)
C++ プログラム例（ABC280E）
考察した漸化式を mod 998244353 で計算しました。
MOD付の演算は、足し算、引き算、掛け算は自然にできますが、割り算は工夫が必要です。フェルマーの小定理を使えば、$N \pmod M$ で割ることは、$N^{M-2} \pmod M$ を掛けることと同じになります。
この計算をするために累乗を計算する関数 power を使います（7ー17行目）。この関数は自前ライブラリとして整備したものです。体力を2減らす確率 critical = p/100 と体力を1減らす確率 normal = 1 – p /100 を先に求めておきます（25、26行目）。
漸化式を素直にプログラムしました。以下が、C++の実装例です。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
#define MOD 998244353
ull power(ull n, ull p, ull mod)
{
if (p == 0) {
return 1;
}
if (p % 2 == 0) {
ull t = power(n, p / 2, mod);
return t * t % mod;
}
return (n * power(n, p - 1, mod))% mod;
}
int main()
{
ull n, p;
cin >> n >> p;
vector<ull> dp(n + 1, 0);
ull critical = (p * power(100, MOD - 2, MOD)) % MOD;
ull normal = (1 + MOD - critical) % MOD;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 2] * critical + dp[i - 1] * normal + 1;
dp[i] %= MOD;
}
cout << dp[n] << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC280E）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 280 E"""
MOD = 998244353
n, p = map(int, input().split())
dp = [0] * (n + 1)
critical = (p * pow(100, MOD - 2, MOD)) % MOD
normal = (1 + MOD - critical) % MOD
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 2] * critical + dp[i - 1] * normal + 1
dp[i] %= MOD
print(dp[n])こちらも「AC」と判定されました。
最後に
確率を用いるDPは、ABC275E問題（解説記事）、ABC323E問題（解説記事）、ABC326E問題（解説記事）と紹介しており、だいぶ慣れてきた気がします。
引き続き ABC の問題を紹介していきます。
