AtCoder Beginners SelectionをC言語で解く

AtCoderで常設で開催されているコンテスト
AtCoder Beginners Selection
をC言語で解いてみました。

自分が提出したコードをほぼそのまま載せていますので、まだまだ改良点はあるかとは思います。

コードの書き方に統一性がないことがありますが、ご容赦ください。

PracticeA：Welcome to AtCoder

この問題は解説する必要がないと思いますので、コードのみ記載します。

#include <stdio.h>
int main(void) {
	int a, b, c;
	char s[110];
	scanf("%d%d%d", &a, &b, &c);
	scanf("%s", s);
	printf("%d %s\n", a + b + c, s);
	return 0;
}

ABC086A：Product

3項演算子を使ってみました。

#include <stdio.h>
int main(void) {
	int a, b;
	scanf("%d%d", &a, &b);
	printf((a * b) % 2 == 0 ? "Even\n" : "Odd\n");
	return 0;
}

ABC081A：Placing Marbles

入力は最大でも3桁しかなく、
各桁は1 or 0のみ入力となるので、
各桁の数を求め、その合計が答えとなります。

#include <stdio.h>
int main(void) {
   int s;
   scanf("%d", &s);
   printf("%d\n",s%10+(s/10)%10+(s/100)%10);
   return 0;
}

ABC081B：Shift only

入力された数字を全て調べて2で割り切れない数があった場合はループを抜け、
そうでない場合、2で割った値で更新、
全て割り切れた場合はインクリメントをし、
ループ抜けるまで繰り返します。
インクリメントした値が答えとなります。

見直してみると最後の方の if(flag==0) は不要ですね。

#include <stdio.h>
int main(void) {
	int n;
	scanf("%d", &n);
	int i, j;
	int a[210];
	for (i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	int flag = 0;
	int count = 0;
	while (flag == 0) {
		for (i = 0; i < n; i++) {
			if (a[i] % 2 != 0) {
				flag = 1;
				break;
			}
			else {
				a[i] /= 2;
			}
		}
		if(flag==0) count++;
	}
	printf("%d\n", count);
	return 0;
}

ABC087B：Coins

計算時間を短くするために、
合計金額がx円を超えた場合と一致した場合はcontinueで一部スキップしています。

#include <stdio.h>
int main(void) {
	int a, b, c;
	int x;
	int count = 0;
	int i, j, k;

	scanf("%d%d%d", &a, &b, &c);
	scanf("%d", &x);
 
	for (i = 0; i <= a; i++) {
		int sum1 = i * 500;
		if (sum1 > x) continue;
		if (sum1 == x) {
			count++;
			continue;
		}
		for (j = 0; j <= b; j++) {
			int sum2 = j * 100;
			if (sum1 + sum2 > x) continue;
			if (sum1 + sum2 == x) {
				count++;
				continue;
			}
			for (k = 0; k <= c; k++) {
				int sum3 = k * 50;
				if (sum1 + sum2 + sum3 > x) continue;
				if (sum1 + sum2 + sum3 == x) {
					count++;
					continue;
				}
			}
		}
	}
	printf("%d\n", count);
	return 0;
}

ABC083B：Some Sums

wa関数を作り、この関数で引数の数字の各桁の和を求めています。
和が範囲内の場合に引数の数字を足すといったことを行っています。

#include <stdio.h>
int wa(int n);
int main(void) {
	int n,a, b;
	int count = 0;
	int i;

	scanf("%d%d%d", &n,&a, &b);
	for (i = 1; i <= n; i++) {
		int sum = wa(i);
		if (a <= sum && sum <= b) count+=i;
	}
	printf("%d\n", count);
	return 0;
}
 
int wa(int n) {
	int sum=0;
	while (n != 0) {
		sum += n % 10;
		n /= 10;
	}
	return sum;
}

ABC088B：Card Game for Two

降順でソートし、
奇数番目(配列の添え字では偶数)のときは足し算
偶数番目(配列の添え字では奇数)のときは引き算
をしたものが答えとなります。
ソートにはqsort関数を使用しました。

#include <stdio.h>
#include <stdlib.h>
int sort(const void* a, const void* b);
int main(void) {
	int n, a[110] = { 0 };
 
 
	int count = 0;
	int i;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	qsort(a, sizeof(a) / sizeof(int), sizeof(int), sort);
	for (i = 0; i < n; i++) {
		if ((i % 2) == 0)  count += a[i];
		else count -= a[i];
	}
	printf("%d\n", count);
	return 0;
}
 
int sort(const void* a, const void* b) {
	return *(int*)b - *(int*)a;
}

ABC085C：Otoshidama

解説とか見たら2重ループで解けることが分かったのですが、
そこまでの頭がなく、3重ループになってしまいました。
goto文使いたくなかったので、フラグを立ててループを抜けています。
計算時間短くするために合計枚数がNを超えた時点でループ抜けています。

#include <stdio.h>
int main(void) {
	long long n, y;
	long long i, j, k;
	int flag = 0;
	scanf("%lld%lld", &n, &y);
 
	for (i = 0; i <= n; i++) {
		for (j = 0; j <= n; j++) {
			if (i + j > n) break;
			for (k = 0; k <= n; k++) {
				if (i + j + k > n)break;
				if ((i * 10000 + j * 5000 + k * 1000) == y&&i+j+k==n) {
					flag = 1;
					break;
				}
			}
			if (flag == 1) break;
		}
		if (flag == 1) break;
	}
 
	if (flag == 0) printf("-1 -1 -1\n");
	else printf("%lld %lld %lld\n", i, j, k);
	return 0;
}

ABC049C：白昼夢

私にとってはかなりの難問で、自力では解けませんでした。
ネット上の解説に書かれていた文字を反転させると文字被りがなくなる
というのを見て解くことができました。
まず入力された文字列を逆順にし、
check_st関数にてあっているかの判別をしています。
check_st関数では、文字がNULL文字になるまでループし、
4種の文字のいずれかに該当したら該当文字数分文字をずらして( ポインターでインクリメントをすることでずらしています )
最終的にNULL文字になったときはYES、途中で4種の文字のいずれにも該当しない場合はNOとして判定を行っています。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int check_st(char* s);
const char* st[] = { "maerd","remaerd","esare","resare" };
int main(void) {
	char s[100010] = { 0 };
 
	scanf("%s", s);
	for (int i = 0; i < (strlen(s)) / 2; i++) {
		char tmp;
		tmp = s[i];
		s[i] = s[strlen(s) - 1 - i];
		s[strlen(s) - 1 - i] = tmp;
	}
 
	
	printf(check_st(s)==0?"YES\n":"NO\n");
	return 0;
}
 
int check_st(char* s) {
	int flag;
	while (s[0] != '\0') {
		flag = 0;
		for (int i = 0; i < 4; i++) {
			if (strncmp(s, st[i], strlen(st[i])) == 0) {
				for (int j = 0; j < strlen(st[i]); j++) {
					s++;
				}
				flag = 1;
				break;
			
			}
			if (s[0] == '\0') break;
		}
		if (flag == 0) return 1;
	}
	return 0;
}

ABC086C：Traveling

この問題も自力では解けませんでした。
ネットで解説しているサイト(言語はRuby)があったので、
そのアルゴリズムを参照して書きました。
このアルゴリズムは非常に参考になりました。

#include <stdio.h>
#include <stdlib.h>
int travel(int t1, int x1, int y1, int t2, int x2, int y2) {
	int mv = 0;
	mv = (t2 - t1) - abs((x1 + y1) - (x2 + y2));
	if (mv < 0) {
		return 1;
	}
	else if (mv % 2 == 0) {
		return 0;
	}
	else {
		return 1;
	}

}

int main(void)
{
	int n;
	int t[100010] = { 0 }, x[100010] = { 0 }, y[100010] = { 0 };

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d%d%d", &t[i + 1], &x[i + 1], &y[i + 1]);
	}
	int flag = 0;
	for (int i = 0; i < n; i++) {
		flag = travel(t[i], x[i], y[i], t[i + 1], x[i + 1], y[i + 1]);
		if (flag == 1) break;
	}

	printf("%s\n", flag == 0 ? "Yes" : "No");

	return 0;
}