AtCoder Beginner Contest 044 by C

AtCoder Beginner Contest 044 について
C言語での回答

atcoder.jp

できたもの
A
B

できなかったもの
C
D

問題A

#include <stdio.h>

int main(void){
    int n,k,x,y;
    scanf("%d %d %d %d", &n, &k, &x ,&y);

    int money;
    if(n>k){
        money =  x*k+(n-k)*y;
    }
    else{
        money = x*n;
    }
    printf("%d", money);
    
    return 0;
}

方針

泊まった日数がK日以下なら宿泊費はX×N円。
K日以上であれば、K日まではX円、残りの日数（N-K）日は(N-K)×Y円なのでその合算を出力します。

問題B

#include <stdio.h>
#include <string.h>

int main(void){
    int i,j;
    char w[101];
    scanf("%s", w);
    int size = strlen(w);

    int count[30]={0};
    for(i=0;i<size;i++){
		count[w[i]-97]++;
    }

    int odd = 0;
    for(i=0;i<27;i++){
        if(count[i]%2!=0){
            odd++;
        }
    }

    if(odd==0){
        printf("Yes");
    }
    else{
        printf("No");
    }

    return 0;
}

方針

入力された文字について、配列countで出てきたアルファベットの要素を加算していきます。
アルファベットは文字コードにし、aを0にするために97を引いています。
後は登場回数が奇数のアルファベットが存在するかを確認し、一文字でも違うのがあればフラグを立てて出力の分岐をします。

問題C

#include <stdio.h>

typedef long long ll;

int main(void){
    int n, a, i, j, k;
    int card[50];
    ll dp[51][51][3010];
    scanf("%d %d", &n, &a);

    for(i=0;i<n;i++){
        scanf("%d", &card[i]);
    }

    dp[0][0][0] = 1;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            for(k=0;k<2500;k++){
                if(dp[i][j][k]){
                    dp[i+1][j][k] += dp[i][j][k];
                    dp[i+1][j+1][k+card[i]] += dp[i][j][k];
                }
            }
        }
    }

    ll ans = 0;
    for(i=1;i<n+1;i++){
        ans += dp[n][i][i*a];
    }
    
    printf("%lld", ans);

    return 0;
}

方針

組み合わせと言えばみんな大好きDPだ！！

以下の様な3次元DPを考えます
dp[i][j][k]：i枚目までのカードでj枚選らんで合計がkである
カードを選ばない　dp[i+1][j][k] += dp[i][j][k]
カードを選ぶ　　　dp[i+1][j+1][k+card[i]] += dp[i][j][k]

選んだカードの平均がAとなるのは総和ｋがj枚×aの時なので、一重ループでdp[n][i][i*a]を数えていけば求まります。

問題D

#include <stdio.h>
#include <math.h>

typedef long long ll;
const ll inf = 1LL << 60;
ll n,s;

ll min (ll aa, ll bb){
    return aa < bb ? aa : bb;
}

ll f(ll b, ll n){
    if(b<2){
        return inf;
    }
    ll ret = 0;
    while(n>=b){
        ret += n % b, n/= b;
    }
    return ret+n;
}

ll solve(){
    if(n == s){
        return n+1;
    }
    ll ans = inf;

    //全探索
    ll b,p;
    for(b=2;b<=sqrt(n);b++){
        if(f(b,n)==s){
            ans = min(ans, b);
        }
    }
    for(p=1;p<=sqrt(n);p++){
        ll B = (n-s)/p + 1;
        if(f(B,n)==s){
            ans = min(ans,B);
        }
    }

    if(ans==inf){
        return -1;
    }
    else{
        return ans;
    }
}

int main(void){
    scanf("%lld %lld", &n, &s);
    
    printf("%lld", solve());
    return 0;
}

方針