AtCoder

ABC275 E問題(Sugoroku 4)を解く

AtCoder_ABC275_E

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

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

E問題 Sugoroku 4(Difficulty : 1264)

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

ABC275 E問題 Sugoroku 4

確率を求めるDPの典型問題でした。AtCoder Problems による Difficulty は、1264 でした。

解答案

dp[i][j] を ルーレットを i 回回したときにマス j にいる確率とします。漸化式は以下となります。

dp[i + 1][j + (1 から m)] += dp[i][j] / m

C++ プログラム例(ABC275E)

考察した漸化式を mod 998244353 で計算しました。

MOD付の演算は、足し算、引き算、掛け算は自然にできますが、割り算は工夫が必要です。フェルマーの小定理を使えば、$N \pmod M$ で割ることは、$N^{M-2} \pmod M$ を掛けることと同じになります。

この計算をするために累乗を計算する関数 power を使います(7ー17行目)。この関数は自前ライブラリとして整備したものです。$M$ で割る場合に掛ける値を変数 invM として計算しておきます(26行目)。

問題の制約から以下の2点に注意します。

  • マス N にいる場合は、ルーネットを回さない(29-33行目)。
  • マス N を超えた場合は、超える分だけ N から引き返す(36ー38行目)。

以下が、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, m, k;
	cin >> n >> m >> k;

	vector<vector<ull>> dp(k + 1, vector<ull>(n + 1, 0));
	dp[0][0] = 1;
	ull invM = power(m, MOD - 2, MOD);
	for (int i1 = 0; i1 < k; ++i1) {
		for (int i2 = 0; i2 <= n; ++i2) {
			if (i2 == n) {
				dp[i1 + 1][i2] += dp[i1][i2];
				dp[i1 + 1][i2] %= MOD;
				continue;
			}
			for (int i3 = 1; i3 <= m; ++i3) {
				int next = i2 + i3;
				if (next > n) {
					next = n - (next - n);
				}
				dp[i1 + 1][next] += dp[i1][i2] * invM;
				dp[i1 + 1][next] %= MOD;
			}
		}
	}


	cout << dp[k][n] << endl;

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC275E)

基本的な考え方は同じです。MOD計算付きの累乗は、組込み関数 pow で計算することができます(7行目)。

"""AtCoder Beginner Contest 275 E"""
MOD = 998244353
n, m, k = map(int, input().split())

dp = [[0 for _ in range(n + 1)] for _ in range(k + 1)]
dp[0][0] = 1
invM = pow(m, MOD - 2, MOD)
for i1 in range(k):
    for i2 in range(n + 1):
        if i2 == n:
            dp[i1 + 1][i2] += dp[i1][i2]
            dp[i1 + 1][i2] %= MOD
            continue
        for i3 in range(1, m + 1):
            nxt = i2 + i3
            if nxt > n:
                nxt = n - (nxt - n)
            dp[i1 + 1][nxt] += dp[i1][i2] * invM
            dp[i1 + 1][nxt] %= MOD

print(dp[k][n])

こちらも「AC」と判定されました。

最後に

確率を用いるDPは、ABC323E問題解説記事)やABC326E問題解説記事)で解いていました。この問題も確率を使うDPとしては、解きやすく感じました。

引き続き ABC を解いていきます。

COMMENT

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

CAPTCHA