ARC060-C 高橋君とカード

問題

C - 高橋君とカード / Tak and Cards

考察

N枚のカードの平均値をちょうどAにしたい

まず、それぞれのカードについて選ぶ場合、選ばない場合を全て探索してそれらの平均がAと一致するかを判定することを考える。これはO(2^n)なのでN≤16の部分点は取れる。(①)

N≤50を満たす解を考える。 組み合わせの総数を求める問題で全探索が使えないならDPを使うとうまくいくことが多いのでDPを考える。

dp[i][j][k]:i番目までの数まででj個選んだときの総数がkとなる組み合わせの総数

dp漸化式:

dp[i+1][j][k]=dp[i][j-1][k-x[i]]+dp[i][j][k]

dp初期条件:dp[0][0][0]=1;

求める値:dp[N][N][A*N]

計算量はO(N^3 *A)これで満点を取ることができる。(②)

(選んだカードの(x[i]-A)の合計が0になる組み合わせをdpする方法でO(N²*A)で解けるようです。)

コード①(200点)

#include<iostream>
using namespace std;

int N,A;
int x[60];

int main(){
    
    cin>>N>>A;
    for(int i=0; i<N; i++)cin>>x[i];
    
    //全てのxiについて選ぶ選ばないを判定
    //bit全探索
    long long ans=0;
    for(long long bit=0; bit<(1<<N); bit++){
        int sum=0,cnt=0;
        for(long long i=0; i<N; i++){
            if(bit & (1<<i)){
                sum+=x[i];
                cnt++;
            }
        }
        double a=(double)sum/(double)cnt;
        if(a==A)ans++;
    }
    
    cout<<ans<<endl;
    
    return 0;
}

コード②(満点)

#include<iostream>
using namespace std;

int N,A;
int x[60];

long long dp[60][60][3600]={};

int main(){
    
    cin>>N>>A;
    for(int i=0; i<N; i++)cin>>x[i];
    
    for(int i=0; i<=N; i++)dp[i][0][0]=1;
    
    for(int i=0; i<N; i++){
        for(int j=1; j<=N; j++){
            for(int k=0; k<=N*A; k++){
                if(k-x[i]>=0){
                    dp[i+1][j][k]+=dp[i][j-1][k-x[i]];
                }
                dp[i+1][j][k]+=dp[i][j][k];
            }
        }
    }
    
    long long ans=0;
    for(int j=1; j<=N; j++){
        ans+=dp[N][j][j*A];
    }
    cout<<ans<<endl;
    
    return 0;
}