AtCoder

ABC280 E問題(Critical Hit)を解く

AtCoder_ABC280_E

AtCoder が提供しているABC(AtCoder Beginner Contest)280 のE問題をC++とPythonで解いてみました。ABC280は、2022年12月3日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

E問題 Critical Hit(Difficulty : 1251)

問題はリンク先をご覧ください。

ABC280 E問題 Critical Hit

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 を解いていきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA