E - Toward 0
/icons/hr.icon
出典
ABC350 - E 1385 diff
/icons/hr.icon
問題
/icons/hr.icon
問題概要
整数$ Nが与えられます。あなたは次の$ 2種類の操作を行うことができる。
$ X円払う。$ Nを $ \left \lfloor \dfrac{N}{A} \right \rfloor に置き換える。
$ Y円払う。$ 1以上$ 6以下の整数が等確率で出るサイコロを振る。その出目を$ bとしたとき、$ Nを$ \left \lfloor \dfrac{N}{b} \right \rfloorに置き換える。
適切に操作を選択したとき、$ Nを$ 0にするまでに払う必要がある金額の期待値の最小値を求めよ。
/icons/hr.icon
制約
$ 1 \leq N \leq 2 \times 10^{18}
$ 2 \leq A \leq 6
$ 1 \leq X, Y \leq 10^9
/icons/hr.icon
考察・解法
メモ化再帰で dfs していけば解けそうだなと感じました
というわけで、まずは dfs で dp をしていくことを考えます。
$ {\mathrm dp} [i] : 整数$ iから$ 0にするまでの期待値の最小値を考えてみます。
$ {\mathrm dp}[0] = 0 です
まずは操作が$ 1つしかない場合を考えます。
$ X円払う場合しかないと考えると、
$ {\mathrm dp}[i] = X + {\mathrm dp} \left[ \left\lfloor \dfrac{N}{A} \right\rfloor \right] と遷移することができます。
コードとしては下記のようになります。
code:python
from collections import defaultdict
def dp(x: int) -> None:
if x == 0:
return 0
return X + dp(x // A)
N, A, X, Y = map(int, input().split())
INF = 10**18
d = defaultdict(lambda: -INF)
print(dp(N))
ここに$ 2種類目の操作が入ってくると、その処理を追加し、それぞれの min を取れば期待値の最小値が求まります。
$ {\mathrm dp}[N] = Y + \dfrac{1}{6}{\mathrm dp \left[ \left\lfloor \dfrac{N}{1} \right\rfloor \right]} + \dfrac{1}{6}{\mathrm dp \left[ \left\lfloor \dfrac{N}{2} \right\rfloor \right]} + \dfrac{1}{6}{\mathrm dp \left[ \left\lfloor \dfrac{N}{3} \right\rfloor \right]} + \dfrac{1}{6}{\mathrm dp \left[ \left\lfloor \dfrac{N}{4} \right\rfloor \right]} + \dfrac{1}{6}{\mathrm dp \left[ \left\lfloor \dfrac{N}{5} \right\rfloor \right]} + \dfrac{1}{6}{\mathrm dp \left[ \left\lfloor \dfrac{N}{6} \right\rfloor \right]}
$ {\mathrm dp}[N] = Y + \dfrac{1}{6} \sum_{i=1}^{6} {\mathrm dp} \left[ \left\lfloor \dfrac{N}{i} \right\rfloor \right]
ここで注意が必要なのが遷移先(右辺)にも$ {\mathrm dp}[i] が含まれているということです。
これは移項することで解決できますね。移項すると左辺が$ \dfrac{5}{6}になるので両辺に$ \dfrac{6}{5}をかけます。
$ {\mathrm dp}[i]= \dfrac{6}{5} \left( Y + \dfrac{1}{6} \sum_{j=2}^{6} {\mathrm dp} \left[ \left\lfloor \dfrac{i}{j} \right\rfloor \right] \right)
これらの$ 2種類の min を取りながら遷移していくことで答えを求めることができます。
したがって、式としては下記のようになります。
$ {\mathrm dp}[i]= \min\left(X + {\mathrm dp} \left[ \left\lfloor \dfrac{i}{A} \right\rfloor \right] , \dfrac{6}{5} \left( Y + \dfrac{1}{6} \sum_{j=2}^{6} {\mathrm dp} \left[ \left\lfloor \dfrac{i}{j} \right\rfloor \right] \right) \right)
ここまでできれば後はやるだけです。
/icons/hr.icon
コード
code:python
from collections import defaultdict
def dp(i: int) -> None:
if i == 0:
return 0
# メモ化で既に値が分かっていればそれを参照する
# 操作 1
p1 = X + dp(i // A)
# 操作 2
p2 = Y
for j in range(2, 7):
p2 += dp(i // j) / 6
p2 *= 6
p2 /= 5
# 2 つの操作の min を取る
# 入力を受け取る
N, A, X, Y = map(int, input().split())
INF = 10**18
d = defaultdict(lambda: -INF)
print(dp(N))
/icons/hr.icon
最後に
※やはり再帰は PyPy よりも Python の方が高速ですね
112ms
26ms