paizaラーニングレベルアップ問題集をC言語でやってみた

paiza×Qiita記事投稿キャンペーンということで、キャンペーン対象問題25問をC言語で解いてみました。

---

文字の一致

#include <stdio.h>
#include <string.h>

int main() {
	char a[101];
	scanf("%s", a);
	char b[101];
	scanf("%s", b);
	puts(strcmp(a, b) ? "NG" : "OK");
	return 0;
}

---

一番小さい値

#include <stdio.h>

int main() {
	int min;
	scanf("%d", &min);
	for (int i = 1; i < 5; i++) {
		int num;
		scanf("%d", &num);
		if (num < min)
			min = num;
	}
	printf("%d\n", min);
	return 0;
}

---

足し算

#include <stdio.h>

int main() {
	int a, b;
	scanf("%d %d", &a, &b);
	printf("%d\n", a + b);
	return 0;
}

---

Eメールアドレス

#include <stdio.h>

int main() {
	char s[65];
	scanf("%s", s);
	char t[65];
	scanf("%s", t);
	printf("%s@%s\n", s, t);
	return 0;
}

---

N倍の文字列

#include <stdio.h>

int main() {
	int n;
	scanf("%d", &n);
	while (n--) {
		putchar('*');
	}
	puts("");
	return 0;
}

---

宝くじ

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

int main() {
	int b;
	scanf("%d", &b);
	int n;
	scanf("%d", &n);
	while (n--) {
		int a;
		scanf("%d\n", &a);
		if (a == b) {
			puts("first");
		} else if (abs(a - b) == 1) {
			puts("adjacent");
		} else if ((a - b) % 10000 == 0) {
			puts("second");
		} else if ((a - b) % 1000 == 0) {
			puts("third");
		} else {
			puts("blank");
		}
	}
	return 0;
}

を三項演算子ならぬ九項演算子で書きました。

#include <stdio.h>

int main() {
	int b;
	scanf("%d", &b);
	int n;
	scanf("%d", &n);
	while (n--) {
		int a;
		scanf("%d\n", &a);
		puts(a==~-b||a==-~b?"adjacent":(a-b)%1000?"blank":(a-b)%10000?"third":a-b?"second":"first");
	}
	return 0;
}

---

野球の審判

#include <stdio.h>

int main() {
	int n;
	scanf("%d", &n);
	int strike = 0;
	int ball = 0;
	while (n--) {
		char s[7];
		scanf("%s", s);
		if (!strcmp(s, "strike")) {
			puts(++strike == 3 ? "out!" : "strike!");
		} else if (!strcmp(s, "ball")) {
			puts(++ball == 4 ? "fourball!" : "ball!");
		}
	}
	return 0;
}

---

みかんの仕分け

#include <stdio.h>

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	while (m--) {
		int w;
		scanf("%d", &w);
		int y = (w + n / 2) / n * n;
		if (!y)
			y = n;
		printf("%d\n", y);
	}
	return 0;
}

---

Fizz Buzz

#include <stdio.h>

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		if (i % 3 && i % 5) {
			printf("%d\n", i);
		} else if (i % 5) {
			puts("Fizz");
		} else if (i % 3) {
			puts("Buzz");
		} else {
			puts("Fizz Buzz");
		}
	}
	return 0;
}

を、三項演算子を使って書きました。

#include <stdio.h>
#include <string.h>

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		if (i % 3 && i % 5) {
			printf("%d\n", i);
		} else {
			char s[10];
			puts(strcat(strcat(strcpy(s,i%3?"":"Fizz"),i%15?"":" "),i%5?"":"Buzz"));
		}
	}
	return 0;
}

更に以下のように書くと警告が出ます。

#include <stdio.h>
#include <string.h>

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		char s[10];
		printf(i%3&&i%5?"%d":"%s",i%3&&i%5?i:strcat(strcat(strcpy(s,i%3?"":"Fizz"),i%15?"":" "),i%5?"":"Buzz"));
		puts("");
	}
	return 0;
}

⇒早速、改善案をコメントして頂きました。有難うございます。

---

残り物の量

#include <stdio.h>

int main() {
	double m, p, q;
	scanf("%lf %lf %lf", &m, &p, &q);
	printf("%.4lf\n", m * (100 - p) * (100 - q) / 10000);
	return 0;
}

---

3Dプリンタ

#include <stdio.h>

int main() {
	int X, Y, Z;
	scanf("%d %d %d", &X, &Y, &Z);
	char s[Z][X][Y+1];
	for (int z = 0; z < Z; z++) {
		for (int x = 0; x < X; x++) {
			scanf("%s", s[z][x]);
		}
		char bar[3];
		scanf("%s", bar);
	}
	while (Z--) {
		for (int y = 0; y < Y; y++) {
			char c = '.';
			for (int x = 0; x < X; x++) {
				if (s[Z][x][y] == '#') {
					c = '#';
					break;
				}
			}
			putchar(c);
		}
		puts("");
	}
	return 0;
}

---

神経衰弱

#include <stdio.h>
#include <string.h>

int main() {
	int H, W, N;
	scanf("%d %d %d", &H, &W, &N);
	int t[H][W];
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			scanf("%d", &t[i][j]);
		}
	}
	int C[N];
	memset(C, 0, sizeof(C));
	int P = 0;
	int L;
	scanf("%d", &L);
	while (L--) {
		int a, b, A, B;
		scanf("%d %d %d %d", &a, &b, &A, &B);
		if (t[--a][--b] == t[--A][--B]) {
			C[P] += 2;
		} else {
			P = -~P % N;
		}
	}
	for (int i = 0; i < N; i++) {
		printf("%d\n", C[i]);
	}
	return 0;
}

---

みんなでしりとり

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

int main() {
	int N, K, M;
	scanf("%d %d %d", &N, &K, &M);
	char D[K][11];
	for (int k = 0; k < K; k++) {
		scanf("%s", D[k]);
	}
	bool alive[N];
	memset(alive, true, sizeof(alive));
	int ans = N;
	char bef[11] = "";
	int P = 0;
	while (M--) {
		char s[11];
		scanf("%s", s);
		if (strlen(bef) && bef[~-strlen(bef)] != s[0] || s[~-strlen(s)] == 'z') {
			alive[P] = false;
		} else {
			for (int k = 0; k <= K; k++) {
				if (k == K) {
					alive[P] = false;
				} else if (!strcmp(s, D[k])) {
					strcpy(bef, s);
					strcpy(D[k], "");
					break;
				}
			}
		}
		if (!alive[P]) {
			ans--;
			strcpy(bef, "");
		}
		do {
			P = -~P % N;
		} while (!alive[P]);
	}
	printf("%d\n", ans);
	for (int i = 0; i < N; i++) {
		if (alive[i]) {
			printf("%d\n", -~i);
		}
	}
	return 0;
}

---

長テーブルのうなぎ屋

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

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	bool seats[n];
	memset(seats, false, sizeof(seats));
	int ans = 0;
	while (m--) {
		int a, b;
		scanf("%d %d", &a, &b);
		bool can_sit = true;
		for (int i = 0; i < a; i++) {
			if (seats[(b + i) % n]) {
				can_sit = false;
				break;
			}
		}
		if (can_sit) {
			for (int i = 0; i < a; i++) {
				seats[(b + i) % n] = true;
			}
			ans += a;
		}
	}
	printf("%d\n", ans);
	return 0;
}

---

名刺バインダー管理

#include <stdio.h>

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	printf("%d\n", 2 * n * ((m - 1) / (2 * n) * 2 + 1) + 1 - m);
	return 0;
}

---

本の整理

#include <stdio.h>

int main() {
	int N;
	scanf("%d\n", &N);
	int A[-~N];
	int B[-~N];
	for (int i = 1; i <= N; i++) {
		scanf("%d", &A[i]);
		B[A[i]] = i;
	}
	int c = 0;
	for (int i = 1; i <= N; i++) {
		if (A[i] != i) {
			B[A[i]] = B[i];
			A[B[i]] = A[i];
			c++;
		}
	}
	printf("%d\n", c);
	return 0;
}

---

山折り谷折り

#include <stdio.h>
#include <string.h>

char* reverse(char* t, const char* s) {
	int n = (int) strlen(s);
	for (int i = 0; i < n; i++) {
		t[i] = '0' + '1' - s[n + ~i];
	}
	t[n] = '\0';
	return t;
}

char* origami(int n, char* s) {
	if (!n) {
		s[0] = '\0';
	} else {
		char t[1 << ~-n];
		strcpy(s, origami(~-n, t));
		strcat(s, "0");
		char u[1 << ~-n];
		strcat(s, reverse(u, t));
	}
	return s;
}

int main() {
	int N;
	scanf("%d", &N);
	char s[1 << N];
	puts(origami(N, s));
	return 0;
}

---

ハノイの塔

#include <stdio.h>

void hanoi(int n, int *k, int *s, int *src, int *d, int *dst, int *t, int *tmp) {
	if (!(*k)) {
		return;
	}
	if (n == 1) {
		dst[(*d)++] = src[--(*s)];
		if (!(--(*k)))
			return;
	} else {
		hanoi(~-n, k, s, src, t, tmp, d, dst);
		hanoi(1, k, s, src, d, dst, t, tmp);
		hanoi(~-n, k, t, tmp, d, dst, s, src);
	}
}

int main() {
	int N, T;
	scanf("%d %d", &N, &T);
	int M[] = {N, 0, 0};
	int piles[3][N];
	for (int i = 0; i < N; i++) {
		piles[0][i] = N - i;
	}
	hanoi(N, &T, M, piles[0], M + 2, piles[2], M + 1, piles[1]);
	for (int i = 0; i < 3; i++) {
		if (!M[i]) {
			puts("-");
		} else {
			printf("%d", piles[i][0]);
			for (int j = 1; j < M[i]; j++) {
				printf(" %d", piles[i][j]);
			}
			puts("");
		}
	}
	return 0;
}

---

じゃんけんの手の出し方

#include <stdio.h>

int min(int a, int b) {
	return a < b ? a : b;
}

int chmax(int *a, int b) {
	if (b > *a) {
		*a = b;
	}
	return *a;
}

int main() {
	int N, M;
	scanf("%d %d", &N, &M);
	char s[-~N];
	scanf("%s", s);
	int G = 0;
	int C = 0;
	int P = 0;
	for (char* c = s; *c; c++) {
		if (*c == 'G') G++;
		else if (*c == 'C') C++;
		else if (*c == 'P') P++;
	}
	int max = 0;
	for (int p = M % 2; p <= M / 5; p += 2) {
		int c = (M - 5 * p) / 2;
		if (c > N) continue;
		int g = N - c - p;
		if (g < 0) continue;
		chmax(&max, min(g, C) + min(c, P) + min(p, G));
	}
	printf("%d\n", max);
	return 0;
}

---

お菓子の詰め合わせ

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

int cmp(const void *p, const void *q) {
	int a = *(int*)p;
	int b = *(int*)q;
	if (a < b) return -1;
	if (a > b) return 1;
	return 0;
}

int N, X, M;
int P[20];

int chmax(int* a, int b) {
	if (b > *a) {
		*a = b;
	}
	return *a;
}

int dfs(int n, int A[], int sum) {
	if (n == M) {
		if (sum <= X) {
			return sum;
		} else {
			return -1;
		}
	} else {
		int max = 0;
		for (int i = (n ? -~A[~-n] : 0); i < N; i++) {
			A[n] = i;
			chmax(&max, dfs(-~n, A, sum + P[i]));
		}
		return max;
	}
}

int main() {
	scanf("%d %d", &N, &X);
	for (int i = 0; i < N; i++) {
		scanf("%d", &P[i]);
	}
	qsort(P, N, sizeof(P[0]), cmp);
	M = 0;
	int S = 0;
	while (M < N) {
		if (S + P[M] > X) {
			break;
		}
		S += P[M++];
	}
	int A[N];
	printf("%d\n", X - dfs(0, A, 0));
	return 0;
}

---

十億連勝

#include <stdio.h>
#include <string.h>

const long MOD = 1000000000;

int main() {
	int n;
	long x;
	scanf("%d %ld", &n, &x);
	long A[n];
	long S[-~n];
	S[0] = 0L;
	for (int i = 0; i < n; i++) {
		scanf("%ld", &A[i]);
		S[-~i] = S[i] + A[i];
	}
	long states[2][-~n];
	memset(states, 0, sizeof(states));
	states[0][0] = 1L;
	for (int i = 0; i < n; i++) {
		long temp[2][-~n];
		memset(temp, 0, sizeof(temp));
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k <= i; k++) {
				long wins = S[i] - S[i - k];
				if (wins > x) {
					break;
				}
				if (wins + A[i] <= x) {
					temp[j][-~k] = (temp[j][-~k] + states[j][k]) % MOD;
					temp[j][0] = (temp[j][0] + A[i] * states[j][k]) % MOD;
				} else {
					temp[1][0] = (temp[1][0] + states[j][k]) % MOD;
					temp[j][0] = (temp[j][0] + (x - wins) * states[j][k]) % MOD;
				}
			}
		}
		memcpy(states, temp, sizeof(temp));
	}
	long answer = 0L;
	for (int i = 0; i <= n; i++) {
		if (S[n] - S[n - i] > x) {
			break;
		}
		answer = (answer + states[1][i]) % MOD;
		if (S[n] - S[n - i] == x) {
			answer = (answer + states[0][i]) % MOD;
		}
	}
	printf("%ld\n", answer);
	return 0;
}

---

文字列収集

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

typedef struct Node {
	int value;
	struct Node *child[26];
} Node;

typedef struct Trie {
	Node *root;
} Trie;

void insert(Trie *trie, const char *key, int value) {
	Node *node = trie->root;
	for (const char *c = key; *c; c++) {
		int ch = (int) (*c - 'a');
		if (!node->child[ch]) {
			if (!(node->child[ch] = (Node*) malloc(sizeof(Node)))) {
				abort();
			}
			memset(node->child[ch], 0, sizeof(Node));
		}
		node->child[ch]->value += value;
		node = node->child[ch];
	}
}

int search(const Trie *trie, const char *key) {
	Node *node = trie->root;
	for (const char *c = key; *c; c++) {
		int ch = (int) (*c - 'a');
		if (!node->child[ch]) {
			return 0;
		}
		node = node->child[ch];
	}
	return node->value;
}

void _clear(Node *node) {
	for (char c = 'a'; c <= 'z'; c++) {
		if (node->child[c - 'a']) {
			_clear(node->child[c - 'a']);
		}
	}
	free(node);
}

void clear(Trie *trie) {
	_clear(trie->root);
	trie->root = NULL;
}

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

	Trie trie;
	trie.root = (Node*) malloc(sizeof(Node));
	memset(trie.root, 0, sizeof(Node));
	while (n--) {
		char s[101];
		int p;
		scanf("%s %d", s, &p);
		insert(&trie, s, p);
	}
	while (m--) {
		char q[101];
		scanf("%s", q);
		printf("%d\n", search(&trie, q));
	}
	clear(&trie);
	return 0;
}

---

mod7占い

#include <stdio.h>
#include <string.h>

int main() {
	int n;
	scanf("%d", &n);
	long C[7];
	memset(C, 0, sizeof(C));
	while (n--) {
		long a;
		scanf("%ld", &a);
		C[a % 7]++;
	}
	long ans = 0L;
	for (int i = 0; i < 7; i++) {
		for (int j = i; j < 7; j++) {
			int k = (14 - i - j) % 7;
			if (k < j) continue;
			if (i == j && j == k) {
				ans += C[i] * (C[i] - 1) * (C[i] - 2) / 6;
			} else if (i == j) {
				ans += C[i] * (C[i] - 1) * C[k] / 2;
			} else if (j == k) {
				ans += C[i] * C[j] * (C[k] - 1) / 2;
			} else {
				ans += C[i] * C[j] * C[k];
			}
		}
	}
	printf("%ld\n", ans);
	return 0;
}

---

島探し

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

const int D[][2] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

void dfs(int h, int w, bool A[h][w], int y, int x) {
	A[y][x] = false;
	for (int d = 0; d < 4; d++) {
		int i = y + D[d][0];
		int j = x + D[d][1];
		if (0 <= i && i < h && 0 <= j && j < w && A[i][j]) {
			dfs(h, w, A, i, j);
		}
	}
}

int main() {
	int M, N;
	scanf("%d %d", &M, &N);
	bool A[N][M];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%hhd", &A[i][j]);
		}
	}
	int c = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (A[i][j]) {
				dfs(N, M, A, i, j);
				c++;
			}
		}
	}
	printf("%d\n", c);	
	return 0;
}

---

村人の友好関係

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

typedef struct Edge {
	int a;
	int b;
	int f;
} Edge;

int cmp(const void* p, const void* q) {
	int a = ((Edge*)p)->f;
	int b = ((Edge*)q)->f;
	if (a < b) return -1;
	else if (a > b) return 1;
	return 0;
}

int root(int* A, int v) {
	if (A[v] < 0)
		return v;
	A[v] = root(A, A[v]);
	return A[v];
}

bool unite(int* A, int v, int u) {
	int rv = root(A, v);
	int ru = root(A, u);
	if (rv == ru) return false;
	if (A[rv] > A[ru]) {
		A[rv] = ru;
	} else {
		if (A[rv] == A[ru])
			A[rv]--;
		A[ru] = rv;
	}
	return true;
}

int main() {
	int N, M, Q;
	scanf("%d %d %d", &N, &M, &Q);
	Edge edges[M];
	for (int j = 0; j < M; j++) {
		scanf("%d %d %d\n", &edges[j].a, &edges[j].b, &edges[j].f);
		edges[j].a--;
		edges[j].b--;
	}
	qsort(edges, M, sizeof(edges[0]), cmp);
	int A[N];
	memset(A, -1, sizeof(A));
	Edge *mst[N];
	memset(mst, 0, sizeof(mst));
	int K = 0;
	while (M--) {
		if (unite(A, edges[M].a, edges[M].b)) {
			mst[K++] = &edges[M];
		}
	}
	bool club[N];
	memset(club, false, sizeof(club));
	while (Q--) {
		char op;
		int q;
		scanf("%c %d\n", &op, &q);
		q--;
		if (op == '+') {
			club[q] = true;
		} else if (op == '-') {
			club[q] = false;
		}
		int p = 0;
		for (int i = 0; i < K; i++) {
			Edge *e = mst[i];
			if (club[e->a] != club[e->b]) {
				p = e->f;
				break;
			}
		}
		printf("%d\n", p);
	}
	return 0;
}