いくつかの要素を抜くDP　No Needから考える - Senの競技プログラミング備忘録

atcoder.jp

この問題から、次のような一般化された問題を考える。

問題文

N個のものを考える。高速でそのうちの1つを抜いた時の計算結果を求める。

概要

この問題は、動的計画法で愚直に計算をするのならば、毎回1つを抜いたものをもとに動的計画法で計算しないといけない。

しかし、これを高速化することが多くの問題では求められる。
高速化に当たって、主に2つの考え方があり、それぞれ応用できる面では一長一短である。

1. 戻すDP

動的計画法には漸化式が存在するが、この時漸化式の演算に逆元が存在するのならば、適宜な計算順序で一つ前に戻すことができる！

例として、パスカルの三角形の漸化式、
$a_{i,j}=a_{i-1,j-1}+a_{i-1,j}$ 、ただし $j= 0, i$ ならば1と定義する。
で、 $a_{1, 1}=1$ から始める。
そして、 $a_{4,0}=1, a_{4,1}=4. a_{4,2}=6, a_{4,3}=4, a_{4,4}=1$ から戻すことを考える。
ひとまず、 $a_{3,0}=1$ である。
次には、 $a_{4,1}$ から逆算して、 $a_{3, 1}$ を計算できて、 $a_{3,1}=a_{4,1}-a_{3,0}=4-1=3$ とわかる。
これと同じように、
$a_{3,2}=a_{4,2}-a_{3,1}=6-3=3$
$a_{3,3}=1$
と二つ目の添え字が小さい順から、逆算できる。

しかし、この手法のデメリットとしては、漸化式の演算が逆元を持たない、例えばmax, min, gcdなどなどの演算であるときは、戻す方法は存在しないこと。
例として、ナップサック問題の漸化式は戻すことが不可能である。

No Needの問題の場合は、
dp[i][j] := i個目まで考慮して、jを作るの場合の数
と定めれば漸化式は
dp[0][0]=1
dp[i][j] = dp[i -1][j] + dp[i - 1][j - a[i]]
となり、加算のみで構成されるので、逆算可能である。
具体的には、
dp[i - 1][j]=dp[i][j]-dp[i - 1][j - a[i]]
である。dp[i - 1][j - a[i]]が定義できない場合は無視すればよいので、この式のjが小さい順から計算できる。

No Needでの解法のソース
Submission #7965931 - AtCoder Beginner Contest 056

2. 両側からDP

i番目のものを抜いたものの計算結果は、1~i - 1番目の結果と i + 1番目から最後までの計算結果を組み合わせたものから計算できる、という点に着目した手法。

事前に左から、右から計算した二つの動的計画法の配列をもっておき、それぞれの結果を組み合わせて計算結果を得るという実装法をとる。

例としては、No Needでは、解説のとおりに
dp[i][j] := i番目まで見て、jを作れるか
と定義した時に、i番目を無視して $[K - a_i, K)$ が作れるかどうかは
dp[i][t]でまず存在し、逆から見たdp2で、 $[K-a_i-t, K - t)$ に作れる値があるのかどうかを確かめる。区間の値の確認は更新が起きないので累積和で簡単に実装できる。