ARC 057 B 高橋君ゲーム
おはやー!(天下ハナビ)。えぬわいです。
続きです。
とりあえず、問題通り、再帰関数を書いてみる。
書いてみる。(ここでバグ見つけて無限に時間かかった)
とりあえず、今日は、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きついな〜と思いました。 ちょっとまだわかんない部分あるんで、また後日解こうと思う。 別の再帰関数で書こうとしたけど、よくわからなかった。理解力ぅ、ですかね。 めげずに頑張ります。