タイトル募集中(DPの問題です)

昨日CodeChefの問題に出てきて分からなかったんですが、有名問題ぽい見た目をしているのにどう検索していいかよく分からなかった。

問題

自然数からなる長さの等しい数列 $\lbrace p_{n} \rbrace$ , $\lbrace q_{n} \rbrace$ であって、次の条件： $\sum p_{i} q_{i} = N$

を満たす時、 $\sum p_{i} + q_{i}$ の最小値を求めよ(数列長は自由に取って良いものとする)。

$dp\lbrack i \rbrack : N=i$ の時の求めたい最小値、とします。

$N$ の小さい場合を手で試してみると、このdpの値には単調性が見られないことが分かります。

$dp\lbrack 1 \rbrack =2 , dp\lbrack 2 \rbrack =3 , dp\lbrack 3 \rbrack =4, dp\lbrack 4 \rbrack = 4 , dp\lbrack 5 \rbrack =6 , dp\lbrack 6 \rbrack = 5 , dp\lbrack 7 \rbrack = 7 ,dp\lbrack 8 \rbrack = 6 …$

といった具合です。

また自明な最小値の上界は $N\times1=N$ を考えると、 $dp\lbrack N \rbrack \leqq N+1$ となります。

数列長が1の場合

$xy=N$ となるような $(x,y,N)$ の組を全て考えればよくて、次のようなコードを書くと計算量の1つが調和級数オーダーで抑えられて、 $O(NlogN)$ で動作します。

for(int i=1;i<=N;i++){
    for(int j=i,t=1;j<=N;j+=i,t++){
        dp[j]=min(dp[j],t+i);
    }
}

数列長が1より大きい場合

上の結果を用いた $O(N^{2})$ のDPで求めることが出来ます。かなり単純なコードになります。

for(int i=1;i<=N;i++){
    for(int j=1;j<i;j++){
        dp[i]=min(dp[i],dp[j]+dp[i-j]);
    }
}

ただ上で紹介した問題では $O(N^{2})$ がTLEしてしまいます。

実は2番目のDPで見るべき遷移は少なく、このオーダーを改善することでAC出来る問題でした(nuipさんのコードでは、内側のループ上限を100に設定して愚直に計算した結果と付き合わせて正当性を確認していました)。

本問題の $N$ の制約下において見るべきDP遷移は、

$dp\lbrack i \rbrack =$ $min(dp\lbrack i \rbrack , dp\lbrack j \rbrack+dp\lbrack i-j \rbrack)$ 　 $1 \leqq j \leqq 2 \sqrt{i}$

に限られるという内容が解説で主張されています。

まだ証明を理解できていないので理解が進んだら書き足します。

touristのACコードの実装が簡潔だったのでこれも紹介。

(理解はこれから…)

const int N=300010;
vector<int> dp(N,0);
int bound=1;
for(int i=1;i<N;i++){
    dp[i]=i+1;
    while((bound+1)*(bound+1)<=i){
        bound++;
    }
    for(int x=bound;x>=1;x--){
        int y=i/x;
        dp[i]=min(dp[i],dp[i-x*y]+x+y);
    }
}

かっつのメモ帳

主に競プロ　時々日記

タイトル募集中(DPの問題です)

問題