Go to Qiita Advent Calendar 2024 Top
LoginSignup
30
28

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@H20inユニークビジョン株式会社

知名度がいまいち分かってないNextDPというテクニックについて

Last updated at Posted at 2024-01-17

はじめに

コード上では変数名としてNDPであったりNextDPと名付けられやすいものです。
正式な名称はよく分かっていないですし、解説されたことがあるのかすら分かっていないテクニックなのですが、どの層でも役に立つもので、使い方やメリットを整理しておこうと思いました。
説明はPythonで行います。ChatGPT-4を使用してC++やRustに置き換えてもらっても動作したので、基本的には別の言語でも使用できるテクニックのはずです。

使い方について

まずは基本的なナップサック問題とそのコードを記載します。
実行速度の差をみたいため制約はすこし大きめです。

問題

$N$ 個の品物があります。それぞれ重さが $w_i$, 価値が $v_i$ です。
重さの総和が $W$ を超えないように選んだ時の価値の総和の最大値を求めなさい。

制約

  • $1 \le N \le 10000$
  • $1 \le W \le 10000$
  • $1 \le w_i \le 10000$
  • $1 \le v_i \le 10^9$
  • 入力は全て整数

一般的なコード(実行時間2000msほど)

import random
random.seed(998244353) 
#NとWが最大のパターンの代わり
N=10000
W=10000
VW = []
for _ in range(N):
    VW.append([random.randint(1, 50),random.randint(1, 50)])
#基本的な解き方
DP = [[0]*(W+1) for _ in range(N+1)] #10001*10001の配列を作る
for i in range(N):
    v,w=VW[i]
    for j in range(W):
        DP[i+1][j]=max(DP[i+1][j],DP[i][j]) #i個目を入れないパターン
        if DP[i][j]>0 and j+w<=W: #i個目を入れるか試すパターン
            DP[i+1][j+w]=max(DP[i+1][j+w],DP[i][j]+v)
    if w<=W:
        DP[i+1][w]=max(DP[i+1][w],v)
print(max(DP[N]))

$DP[i$個目までの商品$][$重さ$]$で、2次元配列で価値の総和の最大を格納しています。
$i$個目までの商品を格納していますが、この遷移にて必要なのは毎回 $i - 1$ の情報のみです。
ずっと全ての情報を保持する必要はないということを考えると以下のように書き換えられます。

NDPを使ったコード(実行時間700msほど)

import random
random.seed(998244353) 
#NとWが最大のパターンの代わり
N=10000
W=10000
VW = []
for _ in range(N):
    VW.append([random.randint(1, 50),random.randint(1, 50)])
#NDPを使用した解き方
DP = [0]*(W+1) #初期配列を作る
for i in range(N):
    v,w=VW[i]
    NDP = [0]*(W+1) #次の遷移先の配列を作成する
    for j in range(W):
        NDP[j]=max(NDP[j],DP[j]) #i個目を入れないパターン
        if DP[j]>0 and j+w<=W: #i個目を入れるか試すパターン
            NDP[j+w]=max(NDP[j+w],DP[j]+v)
    if w<W:
        NDP[w]=max(NDP[w],v)
    DP=NDP #遷移先の配列を現在の配列扱いにする
print(max(DP))

添え字のiとi+1で遷移するのではなく、DPとNDPで遷移していきます。
このような書き方だと2次元配列を使うこともありません。

for i in range(N):
    v,w=VW[i]

は、以下のように書き換えると添え字iもいらなくなります。

for v,w in VW:

NDPを使う場面について

ナップサックは2次元DPになりがちでi個目まで見た値を格納していきますが、2つ前の情報などは気にする必要は基本的にありません。
このように1つ前(2つ前もやろうと思えば可能…)の情報からしか遷移せず、それより前の情報を見ることがない場合のDPに使いがちかなと思います。
難易度が高い問題では大小両方向からアクロバティックに遷移するタイプのDPもあり、そういったDPに対しては使用することは出来ないので注意してください。

効果

  • 添え字を気にする必要が1か所なくなるのでバグが減りやすい
  • DPの次元を1つ落とせるので処理が早くなりTLEしなくなりやすい
  • 巨大な配列を用意する必要が無くなるのでMLEしなくなりやすい

特に2次元配列や3次元配列のアクセスは遅くなりやすいPythonではお勧めの書き方です。

効果の例1

特にPythonで効果があるのでPythonを例にしてみます。
Pythonで競プロを行ってる人が基本躓く問題で確認して見ましょう。
（2020年の問題を未だに擦り続けてるのは老害みたいなものですが…）

Pythonの提出はもちろんTLE、Pypyでは言語アップデートによりギリギリ間に合わないくらいになりましたが、MLEも起きてしまいます。

R,C,K = map(int, input().split())
MAP = [[0] * (C+1) for _ in range(R+1)]
DP  = [[[0] * 4 for _ in range(C+1)] for _ in range(R+1)]
RCV = [list(map(int, input().split())) for _ in range(K)]
for r, c, v in RCV:
    MAP[r-1][c-1] = v
for i in range(R):
    for j in range(C):
        DP[i][j][3]=max(DP[i][j][3],DP[i][j][2]+MAP[i][j])
        DP[i][j][2]=max(DP[i][j][2],DP[i][j][1]+MAP[i][j])
        DP[i][j][1]=max(DP[i][j][1],DP[i][j][0]+MAP[i][j])
        DP[i][j+1][0]=max(DP[i][j+1][0],DP[i][j][0])
        DP[i][j+1][1]=DP[i][j][1]
        DP[i][j+1][2]=DP[i][j][2]
        DP[i][j+1][3]=DP[i][j][3]
        DP[i+1][j][0]=max(DP[i][j])
print(max(DP[R-1][C-1]))
  • Pythonでの提出(TLE)

  • Pypyでの提出(TLEとMLE)

ではこれをNextDPを使用したコードに置き換えてみました。

R,C,K = map(int, input().split())
MAP = [[0] * (C+1) for _ in range(R+1)]
DP  = [[0] * 4 for _ in range(C+1)]
RCV = [list(map(int, input().split())) for _ in range(K)]
for r, c, v in RCV:
    MAP[r-1][c-1] = v
for i in range(R):
    NDP  = [[0] * 4 for _ in range(C+1)]
    for j in range(C):
        DP[j][3]=max(DP[j][3],DP[j][2]+MAP[i][j])
        DP[j][2]=max(DP[j][2],DP[j][1]+MAP[i][j])
        DP[j][1]=max(DP[j][1],DP[j][0]+MAP[i][j])
        DP[j+1][0]=max(DP[j+1][0],DP[j][0])
        DP[j+1][1]=DP[j][1]
        DP[j+1][2]=DP[j][2]
        DP[j+1][3]=DP[j][3]
        NDP[j][0]=max(DP[j])
    DP = NDP
print(max(DP[C-1]))
  • NextDPを使用したPypyでの提出 (2000msほど改善)

効果の例2

1/14にあったE問題の桁DPも1つ前のみからの遷移となるためNDPに置き換えることが可能です。
元が4次元のため、がっつり改善されるわけではないですが、ギリギリTLEしてるパターンについては役立つテクニックだと思います。

  • 元コード (5252ms)

  • NDPコード(4427ms)

ほかの例

setなどでも使えます。直近の問題では以下のような使い方もできます。

N = int(input())
D = []
for i in range(1,13):
    D.append(int('1'*i))
S = set()
S.add(0)
for _ in range(3):
    NS = set()
    for s in S:
        for d in D:
            NS.add(s+d)
    S = NS
print(sorted(S)[N-1])

このテクニックを使ってない方は是非使ってみてください！

追記

この記事公開後にいくつか反応をいただきました。
他に使用される変数名ではdp2、pd、NewDp、PrevDpなど様々な種類があるようです。
C++の挙動など細かいことを理解していなかったこともあり、興味深かったり面白いポストがいくつかあったので以下に並べます。

30
28
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
30
28

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?