[Python] ABC015 D DP 100点
問題 D – 高橋くんの苦悩 回答 動的計画法を使います。 Python では TLE ですが、PyPy では間に合いました。 W = int(input()) N, K = map(int, input().split()) AB =...
「DP」一覧
[Python] ABC015 D メモ化再帰 100点
問題 D – 高橋くんの苦悩 回答 defaultdict defaultdict を使ってみましたが、残念ながらＴＬＥでした。 import collections W = int(input()) N, K = map(int, ...
[Python] ABC011 C
問題 C - 123引き算 回答 全探索は \( 3^{100} \) であり、難しい。 貪欲法 3を引けるときにそれより小さい数字を引く必要はないので、引ける数のうち最も大きな数字を引けば良い。 N = int(input()) N...
[Python] ABC007 D 桁DP
ABC007 Dを桁DPを使って解きます。 桁DP/Digit DP 「n以下の整数の処理」を考えるときに、 大きい桁から一桁ずつ数を見ていき、結果を代入するDP配列に、nより小さいことが確定しているかどうかのフラグを含めることで状態を管理する動的計画法で...