Yukicoder No.23 技の選択

ちゃんと考えれば$O(1)$になるのだろうなあと思って他人の提出等を見たが、だめそう。

solution

次に通常攻撃か必殺技かで場合分けして$\min{}$。$O(H)$。

通常攻撃の場合、$e(h) = 1 + e(h-A)$。 必殺技の場合、$e(h) = 1 + \frac{2}{3}e(h-D) + \frac{1}{3}e(h) = \frac{3}{2} + e(h-D)$。 合わせて$e(h) = \min \{ 1 + e(h-A), \frac{3}{2} + e(h-D) \}$。

implementation

再帰の方がきれいだからと再帰したらsetrecursionlimitが必要になった。

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000+3)
h, a, d = map(int, input().split())
def e(i, memo={}):
    if i <= 0:
        return 0
    else:
        if i not in memo:
            memo[i] = min(1 + e(i-a), 3/2 + e(i-d))
        return memo[i]
print(e(h))