tooh’s diary

半角全角、常体敬体が入り乱れるカオス

AtCoder,AOJ(再帰、dpの初期化)

こんにちは。無気力に日々を過ごしています。とーです。

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の方だと値参照になってしまうため、全部のリストが同じものになってしまう(どこか一か所の変更がすべてに適用されてしまう)という不具合が起こるからです。これのせいで二時間無駄にした。みんなはこんなミスしないようにしようね。