AtCoder Beginner Contest 016(ABC016)

ABC

最近、出張やら新作ゲームやらで手を出せていませんでしたが、今日からABC埋めをぼちぼち再開します、、、。

A – 12月6日

A - 12月6日
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

月が日で割れるかを判断するコードを書きましょう。c++なら%で剰余(余り)が取れます。また、余りが0である場合、割りきれると言えます。

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

using namespace std;
//using namespace atcoder;

int main(){
    int M,D;
    cin>>M>>D;
    if(M%D==0) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

最近のatcoderでは統一されているっぽいですが、YesではなくYESなので気を付けて下さい。(1waくらいました)

B – A±B Problem

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

A+B=C、A-B=Cの2つがそれぞれ成り立つか成り立たないかの4通りで出力を変える問題。素直に実装すればokです。

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

using namespace std;
//using namespace atcoder;

int main(){
    int A,B,C;
    cin>>A>>B>>C;
    if(A+B==C&&A-B==C) cout<<"?"<<endl;
    else if(A+B==C) cout<<"+"<<endl;
    else if(A-B==C) cout<<"-"<<endl;
    else cout<<"!"<<endl;
}

C – 友達の友達

C - 友達の友達
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

入力例の図にある通り、この手の関係はグラフで表せます。グラフで表した際に距離が2であるものが友達の友達と言えそうです。ただ、距離2とと1のルートが両方ある場合、それは友達といえます。逆に、距離2と3の場合は友達の友達と言えます。距離が短い方が採用される感じがするので、最短距離が2である場合は友達の友達といえそうです。

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

using namespace std;
//using namespace atcoder;

int main(){
    int N,M;
    cin>>N>>M;
    vector<int> v[N+1];

    int dat[N+1][N+1];
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(i==j) dat[i][j]=0;
            else dat[i][j]=100000;
        }
    }

    for(int i=0;i<M;i++){
        int A,B;
        cin>>A>>B;
        v[A].push_back(B);
        v[B].push_back(A);
        dat[A][B]=1;
        dat[B][A]=1;
    }



    for(int k=1;k<=N;k++){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                dat[i][j]=min(dat[i][j],dat[i][k]+dat[k][j]);
            }
        }
    }

    for(int i=1;i<=N;i++){
        int c=0;
        for(int j=1;j<=N;j++){
            if(dat[i][j]==2) c++;
        }
        cout<<c<<endl;
    }
}

最短距離を求めるアルゴリズムはたくさんありますが、制約が弱いこと、全頂点間の最短距離が欲しいことからワーシャルフロイドを選択しました。3重forだけで最短距離が求まるお手頃なアルゴリズムです。(ただ、オーダーはN^3と少し重めです)

D – 一刀両断

D - 一刀両断
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

引いた線分が多角形を何箇所切るか、を求めれば良さそうです。入力例2のと凸型の場合、2箇所切っており、1箇所切るごとに1個増えるので2箇所で2個増えて3個になります。線分を追いながら切る箇所を考えると、多角形にに入って出る=多角形と2回交わっている。ように思えます。そのため、この問題は多角形の各辺と線分の交わりの数を数える問題と言えます。

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

using namespace std;
//using namespace atcoder;

int main(){
    double Ax,Ay,Bx,By;
    cin>>Ax>>Ay>>Bx>>By;
    int N;
    cin>>N;
    double X[N+1],Y[N+1];
    for(int i=0;i<N;i++){
        cin>>X[i]>>Y[i];
    }
    X[N]=X[0];
    Y[N]=Y[0];

    int c=0;
    for(int i=1;i<=N;i++){
        double p1x=Ax;
        double p1y=Ay;
        double p2x=Bx;
        double p2y=By;
        double p3x=X[i-1];
        double p3y=Y[i-1];
        double p4x=X[i];
        double p4y=Y[i];
        double pp1=(p1x-p2x)*(p3y-p1y);
        double pp2=(p1y-p2y)*(p1x-p3x);
        double pp3=(p1x-p2x)*(p4y-p1y);
        double pp4=(p1y-p2y)*(p1x-p4x);
        if((pp1+pp2)*(pp3+pp4)<0){
            double pp5=(p3x-p4x)*(p1y-p3y);
            double pp6=(p3y-p4y)*(p3x-p1x);
            double pp7=(p3x-p4x)*(p2y-p3y);
            double pp8=(p3y-p4y)*(p3x-p2x);
            if((pp5+pp6)*(pp7+pp8)<0){
                c++;
            }
        }
    }

    cout<<1+c/2<<endl;
}

線分と線分の交わりは調べたものを適当に書きました。式の意味はイマイチ理解できていないので、要確認ですね、、、。

コメント

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