AtCoder Beginner Contest 204 by C

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

atcoder.jp

コンテスト参加3回目です

できたもの
Ａ
Ｂ

できなかったもの
Ｃ
Ｄ以降

問題A

#include <stdio.h>

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

    if(x==y){
        printf("%d", x);
    }
    else{
        if(x+y==1){
            printf("2");
        }
        else if(x+y==2){
            printf("1");
        }
        else{
            printf("0");
        }
    }
    
    return 0;
}

方針

あいこになるように手を出す問題。
2人の手が同じであれば同じ手を、違えば残りの一つを出します。
違う手の組み合わせはグーとチョキ（0,1）チョキとパー（1,2）パーとグー（2,0）の3通りで、その和が3つとも異なるのでそれを利用して条件分岐します。

問題B

#include <stdio.h>

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

    int total = 0;
    for(i=0;i<n;i++){
        scanf("%d", &a);
        if(a>10){
            total += a-10;
        }
        else{
            continue;
        }
    }

    printf("%d\n", total);

    return 0;
}

方針

入力された木の実の数が10個以下であれば何もせず、10個以上であれば入力された値から10を引いた値を足して総和を出力します。

問題C

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

int road[2001][2001];
bool visited[2001];
int num[2001]={0};

void dfs(int v){
    int i;
    if(visited[v]){
        return;
    }
    visited[v] = true;
    for(i=0;i<num[v];i++){
        dfs(road[v][i]);
    }
}

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

    for(i=0;i<m;i++){
        scanf("%d %d", &a[i],&b[i]);
        a[i]--,b[i]--;
    }
  
    for(i=0;i<m;i++){
        road[a[i]][num[a[i]]] = b[i];
        num[a[i]]++;
    }
  
  int total = 0;
    for(i=0;i<n;i++){
      for(j=0;j<n;j++){
        visited[j] = false;
      }
      dfs(i);
      for(j=0;j<n;j++){
      	if(visited[j]){
          total++;
        }
      }   
    }

    printf("%d\n", total);

    return 0;
}

方針

繋がっている道をDFSで調べ、i番目の町からたどり着ける町をカウントします。既に通った町はvisitedのtrueで判断します。

こっちはTLEになった回答。いまいちどこが原因なのかわからないところ。forで回してvisitedをfalseに初期化してるのは一緒なのでDFSだろうか？

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

bool road[2001][2001];
bool visited[2001];

void reset(int n){
    int i;
    for(i=0;i<n;i++){
        visited[i] = false;
    }
}

int dfs(int v,int n,int c,bool visited[2001]){
    int i;
    visited[v]=true;
    for(i=0;i<n;i++){
        if(road[v][i]==false){
            continue;
        }
        if(visited[i]==true){
            continue;
        }
        c++;
        visited[i] = true;
        c = dfs(i,n,c,visited);
    }
	
    return c;
}

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

    for(i=0;i<m;i++){
        scanf("%d %d", &a,&b);
        a--,b--;
        road[a][b] = true;
    }
  
    reset(n);

  	int count = 0;
        int total = 0;
    //i番目の町をスタートとする時にゴールできる町の数をカウント
    for(i=0;i<n;i++){
        total += dfs(i,n,0,visited);
        total++;
        reset(n);
    }

    printf("%d\n", total);

    return 0;
}

問題D

まだ