AtCoder Beginner Contest 118(ABC118) 解説

ABC

A – B +/- A

A - B +/- A
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

問題文の通りif文で分けて実装します。

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

int main(){
    int A,B;
    cin>>A>>B;
    if(B%A==0) cout<<A+B<<endl;
    else cout<<B-A<<endl;
}

ちょっとお洒落な書き方を思いついたので、コードゴルフついでに実装しました。

#include<stdio.h>
main(){int A,B;scanf("%d%d",&A,&B);printf("%d\n",(A+B)*!(B%A)+(B-A)*!!(B%A));}

ちなみに、真面目にコードゴルフするなら三項演算子の方が短くなります。

#include<stdio.h>
main(){int A,B;scanf("%d%d",&A,&B);printf("%d\n",!(B%A)?A+B:B-A);}

87 Byteでブログを書いている時点では最短です。

B – Foods Loved by Everyone

B - Foods Loved by Everyone
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

Ai1,A12…は異なるという制約があるため、各Aijの食べ物の数をカウントした際、N人が好きな食べ物はカウントがNになるはずです。

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

int main(){
    int N,M;
    cin>>N>>M;

    int c[100]={0};

    for(int i=0;i<N;i++){
        int K;
        cin>>K;
        for(int j=0;j<K;j++){
            int A;
            cin>>A;
            c[A]++;
        }
    }

    int ans=0;
    for(int i=0;i<=M;i++){
        if(c[i]==N) ans++;
    }

    cout<<ans<<endl;
}

C – Monsters Battle Royale

C - Monsters Battle Royale
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

小さい数字が大きい数字を攻撃することで、どんどん小さくできるため基本的に答えは”1″になります。
ただし、入力例のように”1″にならないケースがあります。
それは、各Aiが1以外の倍数であるときです。
Mod a == 0であるもの同士の引き算は答えがMod a == 0になるため、a以下にならなくなります。

各Aiが1以外の倍数であるかを求める方法は色々あるかと思いますが、最大公約数を取るのが一番楽です。

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

int gcd(int a,int b){
    if(a<b) return gcd(b,a);
    if(b==0) return a;
    return gcd(b,a%b);
}
int main(){
    int N;
    int gc;
    cin>>N;
    cin>>gc;
    for(int i=0;i<N-1;i++){
        int A;
        cin>>A;
        gc=gcd(gc,A);
    }

    cout<<gc<<endl;
}

D – Match Matching

D - Match Matching
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

桁数が大きいほうが良いので、使用本数の少ない数字を貪欲に作れば良さそうですが、終端の処理がやや面倒です。
(入力例 3のように、4を3つ作ると余る分で、5や6を作ったほうが良い)

N<=10^4という制約の弱さに着目した場合、各マッチの使用本数に対して、作った数を最大化するDPを作れば良さそうな感じがします。
具体的には、
dp[使用本数]=String
というDPテーブルを持ち、Stringを10進と見た場合に大きくなるように更新していけばOKです。

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

int main(){
    int N;
    cin>>N;
    int M;
    cin>>M;
    int A[M];

    for(int i=0;i<M;i++){
        cin>>A[i];
    }

    int c[10]={0,2,5,5,4,5,6,3,7,6};

    string dp[N+1];
    for(int i=0;i<N+1;i++) dp[i]="";

    for(int i=0;i<N+1;i++){
        if(i==0||dp[i]!=""){
            for(int j=0;j<M;j++){
                string ts=dp[i]+(char)(A[j]+'0');
                int ti=i+c[A[j]];
                if(ti<=N&&(dp[ti].size()<ts.size()||
                   (dp[ti].size()==ts.size()&&dp[ti]<ts))){
                    dp[ti]=ts;
                }
            }
        }
    }
    //for(int i=0;i<N+1;i++) cout<<i<<","<<dp[i]<<endl;
    cout<<dp[N]<<endl;
}

Stringの比較の場合

StrA > StrB

だけだと、Str1=”3333″,Str2=”8″のときに辞書順で後に来るStr2が大きいと判断されます。

StrA.size() > StrB.size() || (StrA.size() == StrB.size() && StrA > StrB)

と桁数の比較をかましましょう。

コメント

タイトルとURLをコピーしました