ARC 057 B 高橋君ゲーム

競技プログラミング

おはやー！(天下ハナビ)。えぬわいです。

qiita.com

続きです。

atcoder.jp

とりあえず、問題通り、再帰関数を書いてみる。

書いてみる。（ここでバグ見つけて無限に時間かかった）

とりあえず、今日は、DPにできそうな再帰関数。

N, K = map(int, input().split())
a = []

for i in range(N):
    a.append(int(input()))


def rec(pos, rest, yesterday):
    """ 機嫌の良い日の最大値を返す """
    if pos == N:
        if rest == 0:
            return 0
        return -100000
    ans = 0
    for i in range(min(a[pos], rest)+1):
        today = (K-rest+i)/sum(a[:pos+1])
        if today > yesterday:
            ans = max(ans, rec(pos+1, rest-i, today)+1)
        else:
            ans = max(ans, rec(pos+1, rest-i, today))
    return ans

print(rec(0, K, 0))

````

この問題では、N 日までに、K 勝しないといけないということに気づかなくて、バグってた。
丁度、K 勝してない時も、普通に返してた。完全に読解ミスです。本当にありがとうございました。

ちなみに、これは、DPにすると、`O(N*K*sum(A))`になるので、時間制限オーバー。

別のDPを考える必要がある。

それは、また明日の記事で。

大学行ってきます。

追記:
解答読んだけど、普通にムズいっすね。

見方を変えるDPきついな〜と思いました。

ちょっとまだわかんない部分あるんで、また後日解こうと思う。

別の再帰関数で書こうとしたけど、よくわからなかった。理解力ぅ、ですかね。

めげずに頑張ります。