AtCoder Beginner Contest 067 by C

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

atcoder.jp

できたもの
A
B
C

できなかったもの
D

問題A

#include <stdio.h>

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

    if(a%3==0||b%3==0||(a+b)%3==0){
        printf("Possible");
    }
    else{
        printf("Impossible");
    }

    return 0;
}

方針

AかBかA＋Bのいずれかの枚数のクッキーを3匹が同じ枚数食べられるように渡せるか
＝AまたはBまたはA＋Bを3で割ったあまりが０になれば可能

よってif文の条件をそのように書いてやればOK

問題B

#include <stdio.h>

int main(void){
    int k,n,i,j,tmp;
    int a[51];
    scanf("%d %d", &n, &k);

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

    for(i=0;i<n;i++){
        for(j=i+1;j<n;j++){
            if(a[i] < a[j]){
                tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
    }

    int sum = 0;
    for(i=0;i<k;i++){
        sum += a[i];
    }
    printf("%d\n", sum);

    return 0;
}

方針

N個の数値からK個選んで総和を最大にする
＝N個の数値を降順で並べ、配列の0番目からK-1番目までの総和を取る

C言語には残念ながらソート機能がないので、2重ループを使って並び替えをしています。
数量の最大値が50なので時間も問題なし。

問題C

#include <stdio.h>

const long long inf = 1LL << 60;

long long abs(long long a){
    return a < 0 ? -a : a;
}

int main(void){
    int n,i,j;
    long long tmp;
    long long a[200001];
    scanf("%d", &n);

    long long sum = 0;
    for(i=0;i<n;i++){
        scanf("%lld", &a[i]);
        sum += a[i];
    }

    long long sunuke = 0, racoon = sum;
    long long min = inf;
    for(i=0;i<n-1;i++){
        sunuke += a[i];
        racoon -= a[i];
        if(abs(sunuke-racoon)<min){
            min = abs(sunuke-racoon);
        }
    }

    printf("%lld\n", min);
    
    return 0;
}

方針

カードの山の上から何枚か取るというのがミソ。
つまり先頭から順番に値を取っていって、取った総和と残った総和の差の絶対値がもっとも小さくなればいいです。

aiを配列に入れ、最初にa1~aNまでの総和を取っておきます。
そこから順に一枚ずつsunukeに足し、racoonから引き、差の絶対値を見ます。
絶対値はabs関数を作り、値が負だった時には符号を逆転しています。

上手くいかなかった点はabs関数の型がintになっていたため、桁あふれしたことです。
あと最初山の上から取るということに気づかず、途中から抜き出す総和……？などといらんことを試案したのがロス。

問題D

#include <stdio.h>
#include <stdlib.h>

int **pass;
int *a;
int *b;
int *c;
int *fennec;
int *sunuke;

//深さ優先探索　t：距離を求める点、u：その親、v：マス1番かＮ番からの距離
void dfs_F(int t,int u,int v) {
    int i;
	fennec[t]=v;
    for(i=0;i<c[t];i++){
		if(pass[t][i]!=u){
          dfs_F(pass[t][i],t,v+1);
        }
    }
}
void dfs_S(int t,int u,int v) {
    int i;
	sunuke[t]=v;
    for(i=0;i<c[t];i++){
		if(pass[t][i]!=u){
          dfs_S(pass[t][i],t,v+1);
        }
    }
}

int main(void){
    int n;
    int i;
    int ans = 0;
    scanf("%d", &n);

    a = (int *)malloc(sizeof(int)*(n-1));
    b = (int *)malloc(sizeof(int)*(n-1));
    c = (int *)malloc(sizeof(int)*n);
    sunuke = (int *)malloc(sizeof(int)*n); 
    fennec = (int *)malloc(sizeof(int)*n);
    pass = (int **)malloc(sizeof(int*)*n);
 
	for(i=0;i<n-1;i++){
		scanf("%d %d",&a[i],&b[i]);
        a[i]--,b[i]--;
      	c[a[i]]++;
      	c[b[i]]++;
	}

    for(i=0;i<n;i++){
  		pass[i]=(int *)malloc(sizeof(int)*c[i]);
   		c[i]=0;
  	}

  	for(i=0;i<n-1;i++){
  		pass[a[i]][c[a[i]]]=b[i];
  	  	pass[b[i]][c[b[i]]]=a[i];
  	  	c[a[i]]++;
  	  	c[b[i]]++;
 	}

	dfs_F(0,-1,0);
	dfs_S(n-1,-1,0);

	for(i=0;i<n;i++){
        ans += (fennec[i] <= sunuke[i]) ? 1 : -1 ;
        free(pass[i]);
    }
    
    free(pass);
    free(a);
    free(b);
    free(c);
    free(fennec);
    free(sunuke);

    printf("%s\n", ans > 0 ? "Fennec" : "Snuke");

    return 0;
}

方針

全ての点において1番のマスからの距離とN番のマスからの距離を計算すると、より距離が短いほうに塗られることになります。
つまり距離が近い点が相手より多ければ勝ちです。

C言語ではvector push_backなどという便利なものはないので代わりに二次元配列を作成。
当然要素数を10^5にすると大きすぎると言われたのでmalloc関数を用いて動的にメモリを確保。

コードについては似たようなことをしていた方の者を参考にしました。

二次元配列に入れたらあとは深さ優先探索でそれぞれの点までの距離を求めます。

今回勉強になったのはループのiはグローバル変数にするとTLEするということでした。
普通関数内で宣言するのでそんなのすることないんですが、まあ処理時間に大きな差が出るんだなあということで一つ。