AtCoder Beginner Contest 054 by C

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

atcoder.jp

できたもの
A
B

できなかったもの
C
D

Bはごり押しが強い気がする

問題A

#include <stdio.h>

int main(void){
    int a,b;
    scanf("%d %d", &a,&b);
    if(a==b){
        printf("Draw");
    }
    else if(a!=1&&b!=1){
        if(a>b){
            printf("Alice");
        }
        else{
            printf("Bob");
        }
    }
    else{
        if(a==1){
            printf("Alice");
        }
        else{
            printf("Bob");
        }
    }
    
    return 0;
}

・値が何であろうと等しければdraw
・1以外は値の大きい方が勝ちなのでどっちが大きいかで条件分岐
・1なら1以外のすべてに勝てるのでそれぞれ1の時で条件分岐

問題B

#include <stdio.h>

int i,j;
char a[51][51], b[51][51];

int check(int m){
    int aa,bb;
    int count = 0;
    for(aa=0;aa<m;aa++){
        for(bb=0;bb<m;bb++){
            if(a[i+aa][j+bb]!=b[aa][bb]){
                count++;
            }
        }
    }
    if(count>0){
        return 1;
    }
    else{
        return 0;
    }
}

int main(void){
    int n,m;
    scanf("%d %d", &n,&m);

    for(i=0;i<n;i++){
            scanf("%s", a[i]);
    }

    for(i=0;i<m;i++){
            scanf("%s", b[i]);
    }

    //b[0][0]と一致するマスがあるか探す
    int match;
    int count = 0;
    int count2 = 0;
    int max = n-m+1;
    for(i=0;i<max;i++){
        for(j=0;j<max;j++){
            if(a[i][j]==b[0][0]){
                count++;
                match = check(m);
                if(match==0){
                    count2++;
                }
            }
        }
    }
    

    if(count==0){
        printf("No");
    }
    else if(count>0&&count2==0){
        printf("No");
    }
    else{
        printf("Yes");
    }

    
    return 0;
}

まずa,bそれぞれの2次元配列に画像の記号1文字ずつをいれます。
そうすることで一致するかどうか判定できます。
n×nの中にm×mが存在するかどうかを調べるのがcheck関数です。
b[0][0]と一致したマスからmの正方形を調べ、全て一致したら0を、1つでも違えば1を返します。
0が返って来た時だけcount2++し、count2が0でなければ1つ以上存在します
またb[0][0]と一致したマスがあればcount++、そもそもなければcount=0のままで条件分岐

解説を見るともっと簡潔に書けるようなのでまた後日。

問題C

#include <stdio.h>
#include <stdbool.h>

#define nmax 8
//隣接行列。つながっていればtrue、つながってなければfalse
bool graph [nmax][nmax];

int dfs(int v, int N, bool visited[nmax]){

    //すべての頂点を訪れたかどうか。訪れていればtrue。まだならfalse
    bool all_visited = true;

    for(int i=0;i<N;i++){
        //iを訪れていたらtrue
        if(visited[i]==false){
            //一つでも訪れてなければfalse
            all_visited = false;
        }
    }

    if(all_visited){
        return 1;
    }
    int ret = 0;

    for(int i=0;i<N;i++){
        //つながっているか。つながってなければcontinue
        if(graph[v][i]==false){
            continue;
        }
        //訪れたことがあるか。あれば（true）continue
        if(visited[i]){
            continue;
        }

        visited[i] = true;
        //次の頂点へ向けて再帰
        ret += dfs(i,N,visited);
        //一番奥までたどり着いたら戻る。終点までたどり着いた場合のみret++でカウント
        //iを訪れてないことにしてi+1の頂点へforループ
        visited[i] = false;
    }

    return ret;
    
}

int main(void){
    int n,m,i,a,b;
    scanf("%d %d", &n, &m);

    for(i=0;i<m;i++){
        scanf("%d %d", &a, &b);
        //つながっているのでtrueを入れる
        graph[a-1][b-1] = graph[b-1][a-1] = true;
    }

    //訪れた場所。訪れたらTrue
    bool visited[nmax];
    for(i=0;i<n;i++){
        visited[i] = false;
    }

    //スタート地点は訪れてるのでtrue
    visited[0] = true;
    printf("%d\n", dfs(0,n,visited));

    
    return 0;
}

無向グラフであること、頂点の数が最大8と少ないことから
隣接行列を使うかなとは思いました。思っただけで終わりましたが。

深さ優先探索によって始点から終点まですべての頂点を一度だけ通ってたどり着けるか、
再帰で求めます。

コードの中にコメント細かく入れました。
頭よすぎて自分じゃこんなのまだ思いつけそうにないです……

問題D

まだ

余談

グラフに関する面白いサイト（記事）
https://qiita.com/maskot1977/items/e1819b7a1053eb9f7d61