AtCoder が提供しているABC（AtCoder Beginner Contest）350 のE問題をC++とPythonで解いてみました。ABC350は、2024年4月20日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Toward 0（Difficulty : 1385）
問題はリンク先をご覧ください。
期待値のDPとして解くことができます。メモ化再帰を使います。AtCoder Problems による Difficulty は 1385 でした。
解答案
問題の見た目が異なりますが、ABC300 E問題（解説記事）は同じような考え方で解くことができました。
dp[i] を整数 i に対して、操作を繰り返して 0 になるまでに支払う金額の期待値とします。2種類の操作のうち2番目の操作だけを考えます。
dp[i] = Y + 1/6(dp[i] + dp[i/2] + dp[i/3] + dp[i/4] + dp[i/5] + dp[i/6])
式を整理すると、以下となります。
dp[i] = 6 / 5 Y + 1/5(dp[i] + dp[i/2] + dp[i/3] + dp[i/4] + dp[i/5] + dp[i/6])
また、dp[0] = 0 です。この式に1番目の操作も加えます。ふたつの操作の結果で小さい値が dp[i] となります。dp[N] が解となります。
C++ プログラム例（ABC350E）
今回はDPを再帰を使って実装します。素の実装では間に合わないため、メモ化再帰を使います。
再帰関数の補足です。
- 引数が０なら0を返す。
- メモとして記憶されているならメモの値を返す。
- そうでないなら、漸化式に従って再帰的に値を計算する（19ー23行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
ull n, a, x, y;
map<ull, double> memo;
double rec(ull n)
{
if (n == 0) {
return 0.0;
}
if (memo.find(n) != memo.end()) {
return memo[n];
}
double t = 6.0 / 5.0 * (double)y;
for (int i = 2; i <= 6; ++i) {
t += rec(n / i) / 5.0;
}
double result = min((double)x + rec(n / a), t);
memo[n] = result;
return result;
}
int main()
{
cin >> n >> a >> x >> y;
cout << fixed << setprecision(15);
cout << rec(n) << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC350E）
Python 3.9 以降では、cache というデコレータが使えます（2、5行目）。メモ化再帰の処理が隠されたため、すっきりと書けています。以下となります。
"""AtCoder Beginner Contest 350 E"""
import functools
@functools.cache
def rec(n):
global a, x, y
if n == 0:
return 0.0
t = 6.0 / 5.0 * y
for i in range(2, 7):
t += rec(n // i) / 5.0
result = min(x + rec(n // a), t)
return result
n, a, x, y = map(int, input().split())
print(rec(n))こちらも「AC」と判定されました。
最後に
Pythonのデコレータを紹介するのは３回目です。ABC275D問題とABC340C問題でした。メモ化再帰もそれだけ使っていることになります。繰り返して使っていれば習得できると考えています。
引き続き ABC の問題を紹介していきます。
