Naomi's notebook

Naomi's notebook

半分全列挙（DP）(ABC054D - Mixing Experiment)

競プロ

ところでD問題って（n年前の感覚としては）普通に解けるような感覚でいたけど結構厳しい
精進をn年もサボっていたせいですね

atcoder.jp

二通りのやり方で解きました。

半分全列挙

全探索すると2^40かかる。
半分全列挙すると2^21かかる。難しいこと考えずにこれで良いか…
具体的には、a:b=M_a:M_bの時b \times M_a - a \times M_b =0となるので、これを半分ずつ全ての可能性求めておき、半分を定めればもう半分の選び方は二分探索でいける。
計算量はO(2^{N/2}N)だいたい10^7~10^8

何個もWAを出してしまった。半分全列挙の時はその半分の中から使わないということを表すコスト0、値0を入れるんだけど、今回ソートの関係で、半分ずつb \times M_a - a \times M_b =0が成り立つ場合強制的にそれが選ばれてしまう場合があり、実際はCを作ることが可能なのに-1を出力してしまう例外がなかなか取り除けなかった為である。（説明が適当なのですがコードを見ればわかります）

        if(ite+1<H2.size()&&H1[i].second+H2[ite+1].second!=0&&H1[i].first+H2[ite+1].first==0){
            ans=min(ans,H1[i].second+H2[ite+1].second);
        }

を挿入して解決。

#include <stdio.h>
#include <stdlib.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>
 
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define LLIandI pair<long long int , int>
#define ll long long


int main(void){
    int N,Ma,Mb;
    scanf("%d %d %d",&N,&Ma,&Mb);
    int A[50],B[50],C[50];
    rep(i,N){
        scanf("%d %d %d",&A[i],&B[i],&C[i]);
    }
    //Asum*Mb-Bsum*Ma=0
    vector< pair<int, int> > H1;
    vector< pair<int, int>  > H2;
    rep(i,1<<(N/2)){ //0...N/2-1 (N/2)
        int ABh=0,Ch=0;
        rep(j,N/2){
            ABh+=Mb*A[j]*( (i>>j)%2 );
            ABh-=Ma*B[j]*( (i>>j)%2 );
            Ch+=C[j]*( (i>>j)%2 );
        }
        H1.pb(mp(ABh,Ch ) );
    }
    rep(i,1<<(N-N/2) ){//N/2...N-1 (N-N/2)
        int ABh=0,Ch=0;
        rep(j,(N-N/2)){
            ABh+=Mb*A[j+N/2]*( (i>>j)%2 );
            ABh-=Ma*B[j+N/2]*( (i>>j)%2 );
            Ch+=C[j+N/2]*( (i>>j)%2 );
        }
        H2.pb(mp(ABh,Ch) );
    }
    sort(H1.begin(),H1.end());sort(H2.begin(),H2.end());
    int ans=1001001001;
    rep(i,H1.size()){
        int ite=lower_bound(H2.begin(),H2.end(),mp(-H1[i].first,-1) )-H2.begin();
        if(ite<H2.size()&&H1[i].second+H2[ite].second!=0&&H1[i].first+H2[ite].first==0){
            ans=min(ans,H1[i].second+H2[ite].second);
        }
        if(ite+1<H2.size()&&H1[i].second+H2[ite+1].second!=0&&H1[i].first+H2[ite+1].first==0){
            ans=min(ans,H1[i].second+H2[ite+1].second);
        }
    }
    if(ans==0||ans==1001001001)printf("%d\n",-1);
    else printf("%d\n",ans);
}

動的計画法

思考停止半分全列挙してしまったけど
なんかナップサックっぽいし動的計画法で他の解き方がありそう
解説をちらっと見たらやっぱりそっちが想定解ではあるのであとで考えます。


というわけでやりました。DPだということを確認して解いたので完全には自分で考えていません。
計算量はN*(|sum( M_a*B-M_b+A) | ) = N*(2*max(M_a)*max(M_b)*N) = N^2*max(M_a)*max(M_b)
(面倒臭いのでmax(M_a)=max(M_b)=10,max(a_i)=max(b_i)=10に実際の計算量は固定しています。)


またWAを量産したので調べてみたらやっぱり最初からいくらかを使わない時の例外処理ができていませんでした。まずsum( M_a*B_i-M_b*A_i )=0に最終的になってしまった時は使っていないだけなのでダメです。さらに、最初からいくらかを使わない時については、コストが0の状況は継承しないことにしてから、dp[i][M_a*B_i-M_b*A_i]=min( 同上,c)とすることで、そこまでが0であった場合に対応できます。（これは解説を見てやっとわかりました…デバッグ力をあげたい）

#include <stdio.h>
#include <stdlib.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>
 
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define LLIandI pair<long long int , int>
#define ll long long

//DPバージョン
int main(void){
    int N,Ma,Mb;
    scanf("%d %d %d",&N,&Ma,&Mb);
    int A[50],B[50],C[50];
    int dp[41][41*11*11*2];
    //dp[i][j]=m i番までの薬品を使ってM_a*b-M_b*a(絶対値N(=40)*Ma,Mb(=10)*max(a),max(b)(=10)=4000以下)=Jにしたときの最低のコストがmということを表す
    //Jについては、添字jについてJ=k-N*10*10とする。(kは0以上2*N*10*10以下 )
    rep(i,N)rep(j,N*10*10*2+1)dp[i][j]=INF;
    rep(i,N){
        scanf("%d %d %d",&A[i],&B[i],&C[i]);
        if(i==0){
            dp[i][N*100]=0;
            dp[i][N*100+Ma*B[i]-Mb*A[i]]=C[i];
        }
    }
    rep(i,N){
        rep(k,2*100*N+1){
            //i-1番めまでは一切使わない時の例外処理
            dp[i][ N*100+Ma*B[i]-Mb*A[i] ]=min(C[i], dp[i][ N*100+Ma*B[i]-Mb*A[i] ] );
            if(i<N-1){
                if(dp[i][k]==0)continue;//i番目までは全く使っていないものについては上で処理するので継承しない
                int newJ=Ma*B[i+1]-Mb*A[i+1];
                //i+1を使う時
                dp[i+1][k+newJ]=min(dp[i][k]+C[i+1], dp[i+1][k+newJ] );
                //i+1を使わない時
                dp[i+1][k]=min(dp[i][k],dp[i+1][k]);
            }
            
        }
    }
    
    if(dp[N-1][N*100]>=INF||dp[N-1][N*100]<=0)printf("%d\n",-1);
    else printf("%d\n",dp[N-1][N*100]);
}





オマケ

f:id:Naomi_Lilienthal:20190330012740p:plain
ひどい。