こんにちは。無気力に日々を過ごしています。とーです。
ABC115D
バンズとパティだけで構成されるハンバーガーをめっちゃ重ねて、その下からX層を食べるとパティは何枚食べられますか、という問題。ちなみに僕はチーズバーガーが大好きです。
解き方は、「レベルNバーガー」という情報と「下からX枚食べる」という2つの情報から、何枚パティを食べることになるかに重きを置いて考えれば、パティの枚数を求めるf(N,X)という関数を定義すればよいことになる。
まず、レベル1~Nバーガーについて、「何枚の層で構成されているか」というリストaと、「何枚のパティが入っているか」というリストpを作る。最初はa = [1]、p = [1]で、
a[i+1] = 2*a[i]+3
p[i+1] = 2*p[i]+1
で求めていけばよい
レベルNバーガーは構成的には「バンズ：N-1バーガー：パティ：N-1バーガー：バンズ」となっているので、
N != 0において、（N==0は適当に求める）
ア：X == 1なら、当然0（一番下のパンしか食べられない。悲しい）
イ：1 < X <= 1+a[N-1]なら（つまりパン＋レベルN-1バーガーまでなら）、f(N-1,X-1)を返す（N-1バーガーの下からX-1層を食べる。Xから一番下のパンを引いておくことに注意）
ウ：X == 2+a[N-1]なら（パン＋レベルN-1バーガー＋ど真ん中のパティなら）、p[N-1]+1を返す
エ：2+a[N-1] < X <= 2+2*a[N-1]なら（パン＋レベルN-1バーガー＋パティ＋レベルN-1 バーガーまでなら）、p[N-1]+1+f(N-1,X-2-a[N-1])を返す（これもイと同様の考え方）
オ：X = 3+2*a[N-1]なら（全部食べる）、2*p[N-1]+1を返す
これを愚直に書けばよい。少なくとも次はN-1バーガーについて調べることになるので、N+1回以下のステップで答えが求まる。
DPL_1_B
ナップザック問題 | 動的計画法 | Aizu Online Judge
以下のa,bのうち、どちらが正しいコードでしょうか
a
n,w = map(int,input().split()) L = [] for i in range(n): L.append(list(map(int,input().split()))) dp = [] for i in range(n+1): T = [0]*(w+1) dp.append(T) for i in range(n-1,-1,-1): for j in range(w+1): if j < L[i][1]: dp[i][j] = dp[i+1][j] else: dp[i][j] = max(dp[i+1][j],dp[i+1][j-L[i][1]]+L[i][0]) print(dp[0][w])
b
n,w = map(int,input().split()) L = [] for i in range(n): L.append(list(map(int,input().split()))) dp = [] T = [0]*(w+1) for i in range(n+1): dp.append(T) for i in range(n-1,-1,-1): for j in range(w+1): if j < L[i][1]: dp[i][j] = dp[i+1][j] else: dp[i][j] = max(dp[i+1][j],dp[i+1][j-L[i][1]]+L[i][0]) print(dp[0][w])
正解はa
なんでかというと、aでは「n+1回、0埋めしたリストTを作ってappend」しているが、bでは「0埋めしたリストTを作って、n+1回append」しているという違いがあり、bの方だと値参照になってしまうため、全部のリストが同じものになってしまう（どこか一か所の変更がすべてに適用されてしまう）という不具合が起こるからです。これのせいで二時間無駄にした。みんなはこんなミスしないようにしようね。
