AtCoder Beginner Contest 044/AtCoder Regular Contest 060

atcoder

はい。
https://atcoder.jp/contests/abc044

A - 高橋君とホテルイージー / Tak and Hotels (ABC Edit)

C++14

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n,k,x,y;
    scanf("%d",&n);
    scanf("%d",&k);
    scanf("%d",&x);
    scanf("%d",&y);
    printf("%d\n",x*min(n,k)+max(y*(n-k),0));
 
    return 0;
}

問題文の通りに計算する。k+1泊目以降からyになるのを慎重に計算すれば大丈夫そう。

B - 美しい文字列 / Beautiful Strings

C++14

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    char w[101];
    int chk[26]={0};
    scanf("%s",w);
    for (int i=0;i<strlen(w);i++){
        chk[w[i]-'a']++;
    }
    for (int i=0;i<26;i++) {
        if (chk[i]%2) {
            printf("No\n");
            return 0;
        }
    }
    printf("Yes\n");
    return 0;
}

各文字の出現回数を数え終わってから奇数回のものがないかを確認してYes/No判定すれば大丈夫そう。

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

C++14(部分点解)

#include<bits/stdc++.h>
 
using namespace std;
//部分点のみ用
int main(){
    int n,a,cnt,ttl;
    long long ans=0;
    scanf("%d %d",&n,&a);
    vector<int> x(n);
    for (auto&e:x) scanf("%d",&e);
 
    for (int i=0;i<(1<<n);i++) {
        cnt=0;
        ttl=0;
        for (int j=0;j<n;j++) {
            if (i & (1<<j)) {
                cnt++;
                ttl+=x[j];
            }
        }
        if (cnt*a==ttl && ttl!=0) ans++;
    }
    printf("%lld\n",ans);
 
    return 0;
}

C++14(満点解法1、N3 * X)

#include<bits/stdc++.h>

using namespace std;
int main(){
    //([n][n][n*x] -> n^3 * x)
    long long dp[51][51][2501];
    for (int i=0;i<51;i++) for (int j=0;j<51;j++) for (int k=0;k<2501;k++) dp [i][j][k]=0;
    dp[0][0][0]=1;
    int n,a,x;
    long long ans=0;
    scanf("%d %d",&n,&a);
    for (int i=0;i<n;i++) {
        scanf("%d",&x);
        for (int j=0;j<50;j++) {
            for (int k=0;k<2501;k++) {
                if (dp[i][j][k]){
                    dp[i+1][j][k]+=dp[i][j][k];
                    dp[i+1][j+1][k+x]+=dp[i][j][k];
                }
            }
        }
    }
    for (int i=1;i<=n;i++) ans+=dp[n][i][i*a];
    printf("%lld\n",ans);
    return 0;
}

PyPy3

def sol():
    n,a=map(int,input().split())
    x=[int(i) for i in input().split()]
    ans=chk=0
    d=[[0]*2501 for j in range(51)]
    d[0][0]=1
    for i in x:
        for j in range(2500,i-1,-1):
            for k in range(50,0,-1):
                d[k][j]+=d[k-1][j-i]
    for i in range(1,51):
        ans+=d[i][i*a]
    print(ans)
 
if __name__=="__main__":
    sol()

部分点はそれぞれのカードを使う使わないで合計が、平均がいくつになるかで1パターンずつ数える。これはテストケースが大きくなるとTLEに。満点解法その1はN3 * xでdp[j][k][s]でk枚選んで合計をsに〜らしい。なるほどわからんという感じ。 3次元配列を0で初期化してないだけで2時間位無駄にしました。
久しぶりに解き直してPythonで書いたら2次元配列で出来ました。[0][0]はカード0枚で合計0が1通りと他は全て0で初期値を設定します。カードを1枚ずつ取り出しながらk枚のカードで合計jになるかを調べて、最後にi枚使って合計がi×aのものの総和が解になるはずです。多分。あと配列は枚数、合計が多い方から更新しないとマズい気がします。

D問題はあとで