AtCoder振り返りその5（AtCoder Beginner Contest 308）

まえがき

競技プログラミング振り返り5回目となります。
今回解けたのはA,B問です、以下はその内容の振り返りとなります。

A問(New Scheme)

問題はこちら→A - New Scheme

与えられた数字がすべての条件を満たすか確認するだけですね。

A問提出コード

#include <stdio.h>

int main(void)
{
	int s;
	int temp = 100;
	for (int i = 0; i < 8; i++)
	{
		scanf("%d", &s);
		if (s%25 != 0 || s <temp || s>675 )
		{
			printf("No\n");
			return 0;
		};
		temp = s;
	}
	printf("Yes\n");
	return 0;
}

条件の中で数字が抗議単調増加であること前提とした場合、始めの数字のみ100以上であればよいため
tempに100を入れて置き条件を満たしていれば比較した数字を入れて次の数字の入力に移る形となります。
tempという変数名よりかminなどのほうが適切だったかもしれません。

B問(Default Price)

問題はこちら→B - Default Price

回転寿司でたべたお皿の合計を出す問題です。
食べたお皿ごとに金額が違うためそれを踏まえて合計をだします。

B問提出コード

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

int main(void)
{
	int n, m;
	char c[100][21]={ 0 };
	char d[100][21]={ 0 };
	int p[100];
	int ans =0;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		scanf("%s", &c[i]);
	}
	for (int i = 0; i < m; i++)
	{
		scanf("%s", &d[i]);
	}
	for (int i = 0; i < m+1; i++)
	{
		scanf("%d", &p[i]);
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (!strcmp(c[i], d[j])) {
				ans += p[j+1];
				break;
			}
			if (m - 1 == j)
			{
				ans += p[0];
			}
		}
	}
	printf("%d", ans);

	return 0;
}

入力後に二重for文内でstrcmpを使い照合しています。

感想

C問に挑戦してみましたが、ソートにバブルソートを使用し時間超過のためできませんでした。
バブルソート以外のソートを使えるようになるべきですね。

AtCoder振り返りその4（AtCoder Beginner Contest 307）

まえがき

競技プログラミング振り返り4回目となります。
今回解けたのはA,B問のみのため以下はその内容の振り返りとなります。

A問(A - Weekly Records)

問題はこちら→A - Weekly Records

7日ごとの合計を出せばいいだけですね

A問提出コード

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

int main(void)
{
	int week;
	int sum[10] = { 0 };
	scanf("%d", &week);
	for (int i = 0; i < week; i++)
	{
		for (int j = 0; j < 7; j++)
		{
			int a;
			scanf("%d", &a);
			sum[i] += a;
		}
	}
	for (int i = 0; i < week; i++)
	{
		printf("%d ", sum[i]);
	}
	return 0;
}

二重for文で入力をとっているだけですね。

B問(B - racecar)

問題はこちら→B - racecar

N個の文字列が与えられるので、与えられた文字列の内異なる二つの文字をつなげて回文が成立する組み合わせがあるか判定します。

B問提出コード

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



int main(void)
{
	int n;
	char s[101][51];
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%s", s[i]);
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			{
				char palindrome[101] = { 0 };
				strcpy(palindrome, s[i]);
				strcat(palindrome, s[j]);
				int palong = strlen(palindrome);
				for (int k = 0; k < (n + 1) / 2; k++)
				{
					if (palindrome[k] != palindrome[palong - 1 - k])
					{
						break;
					}
					if (k + 1 == (n + 1) / 2)
					{
						printf("Yes\n");
						return 0;
					}

				}
			}
			{
				char palindrome[101] = { 0 };
				strcpy(palindrome, s[j]);
				strcat(palindrome, s[i]);
				int palong = strlen(palindrome);
				for (int k = 0; k < (n + 1) / 2; k++)
				{
					if (palindrome[k] != palindrome[palong - 1 - k])
					{
						break;
					}
					if (k + 1 == (n + 1) / 2)
					{
						printf("Yes\n");
						return 0;
					}
				}
			}
		}
	}
	printf("No\n");
	return 0;
}

二重for文を使い異なる文字列のみstrcpyとstrcatを使い判定を行うための文字列を作成し、for文で一文字ずつ見ていきます。

感想

今回解けたのはA,Bのみですが今回のB問はなかなか解きがいがありました。

AtCoder振り返りその3(AtCoder Regular Contest 162)

まえがき

競技プログラミング振り返り三回目となります。
時間内には解けませんでしたが、なんとかA問のみ解けたので振り返ります。

A問(A - Echo)

問題はこちら→A - Ekiden Race

復路が一番早い可能性がある人数を出力するものです。
問題文で説明されていない、3つ目のテストケースを用いて解説を行います。

往路	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
復路
往復	13	2	7	1	5	9	3	4	12	10	15	6	8	14	20	16	19	18	11	17

順位にを表に直すとこのようになります。
往路の順位と往復の順位がわかりますね、復路の順位は分からないので、一番早い可能性があれば○をそうでなければ×を入れます。
往路の昇順でならんでいますが、往復の昇順が処理と説明の都合よいので並び替えたものも用意します。

往路	4	2	7	8	5	12	3	13	6	10	19	9	1	14	11	16	20	18	17	15
復路
往復	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

往復の順位に並び替えたことにより少しわかりやすくなりました。
復路が一番早い可能性がある人を数えていくのですが、消去法でその可能性がない人を消していきます。
条件としてはだれかと比較して往路の順位が高く往復の順位が低い人が対象となります。
分かりやすくいうと復路で抜かされた人です、それ以外の人は復路が一番早い可能性がある人となります。

往路	4	2	7	8	5	12	3	13	6	10	19	9	1	14	11	16	20	18	17	15
復路	○	×
往復	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

左から見ていき2番目で復路で抜かされた人がでてきました。

往路	4	2	7	8	5	12	3	13	6	10	19	9	1	14	11	16	20	18	17	15
復路	○	×	○
往復	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

3番目の人は抜かされていないので○です。なぜ簡単にわかるかという往復が高い順位(左)から見ていくため、往路の順位をみて自分より左(往復が高い順位)に往路の順位が低い人がいれば×、いなければ○となります。
これをプログラミングで行う際は変数MAXに都度往路が低い順位を入れていき判定をおこないます。いまだとMAXに7が入っています。

往路	4	2	7	8	5	12	3	13	6	10	19	9	1	14	11	16	20	18	17	15
復路	○	×	○	○
往復	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

MAXに8が入っています。

往路	4	2	7	8	5	12	3	13	6	10	19	9	1	14	11	16	20	18	17	15
復路	○	×	○	○	×	○	×	○	×	×	○	×	×	×	×	×	○	×	×	×
往復	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

すべて埋めたものがこちらになります、ちゃんと出力例の通りに7人出ていますね。
上記の流れを行うと以下のようなコードになります。

A問提出コード

#include<stdio.h>

int main() {
	int t;
	int ans[500];
	
	scanf("%d", &t);
	for (int j = 0; j < t; j++)
	{
		int n, count = 0, max = 0;
		int p[1000];
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
		{
			int temp;
			scanf("%d", &temp);
			p[temp - 1] = i;
		}
		for (int i = 0; i < n; i++)
		{
			if (p[i] >= max)
			{
				max = p[i];
				count++;
			}
		}
		ans[j] = count;
	}
	for (int i = 0; i < t; i++)
	{
		printf("%d ", ans[i]);
	}
	return 0;
}

for内の最初のfor文で入力と同時に往復の昇順に配列をならべかえています。
その後説明した通りの流れで見ていき○があればcountを1増やしています。

感想

時間内に解くことはできませんでしたが、自身の力で解けたのでよしとします。

AtCoder振り返りその2（AtCoder Beginner Contest 306）

まえがき

競技プログラミング振り返り二回目となります。
今回解けたのはA,B,C問のみのため以下はその内容の振り返りとなります。

A問(A - Echo)

問題はこちら→A - Echo

A問提出コード

#include<stdio.h>

int main() {
	int n;
	char s[51];
	scanf("%d", &n);
	scanf("%s", s);
	for (int i = 0; i < n; i++)
	{
		printf("%c%c", s[i], s[i]);
	}
	return 0;
}

for文で2文字ずつ出しているだけですね。
これだけじゃちょっとつまらなかったので別のコードも書いてみました。

A問別コード

#include<stdio.h>

int main() {
	int n;
	char s[101] = { 0 };
	scanf("%d", &n);
	for (size_t i = 0; i < n * 2; i++)
	{
		scanf(" %c", &s[i]);
		i++;
		s[i] = s[i - 1];
	}
	printf("%s\n", s);
	return 0;
}

入力時に２文字ずつ配列に入れて最後に文字列を出しています。

B問(B - Base 2)

問題はこちら→B - Base 2

符号なし64bit整数を２進数で入力して、10進数に直す問題ですね。

B問提出コード

#include<stdio.h>
#include<math.h>
int main() {
	int num[65];
	unsigned long long ans = 0;
	for (int i = 0; i < 64; i++)
	{
		scanf("%d", &num[i]);
	}
	for (int i = 0; i < 64; i++)
	{
		if ((int)num[i])
		{
			ans += (unsigned long long)pow(2, (double)i);
		}
	}
	printf("%llu\n", ans);
	return 0;
}

入力後に一文字ずつ見ていき、for文で桁数に合わせて1であれば足し算をしています。

B問提出コード(改善)

#include<stdio.h>
#include<math.h>
int main() {
	int num;
	unsigned long long ans = 0;
	for (int i = 0; i < 64; i++)
	{
		scanf("%d", &num);
		if (num)
		{
			ans += (unsigned long long)pow(2,(double)i);
		}
	}
	printf("%llu\n", ans);
	return 0;
}

for文を1つにして入力を保持しない形に直しました。

B問別回答

#include<stdio.h>

int main() {
	unsigned long long ans = 0, num;
	for (int i = 0; i < 64; i++)
	{
		scanf("%llu", &num);
		if (num)
		{
			ans += num << i;
		}
	}
	printf("%llu\n", ans);
	return 0;
}

シフト演算子を使ってみました、あまり使う機会が少ないのでこのような問題はありがたいですね。

C問(C - Centers)

問題はこちら→C - Centers

1からNまでの整数が3個づつ、長さ3Nの数列にランダム並びで入っており。1からNまでの整数を2回目に出てくる並びで出力するものです。

C問提出コード

#include<stdio.h>
#include<math.h>
int main() {
	static int num[1500000];
	static int num2[500000] ={ 0 };
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n * 3; i++)
	{
		scanf("%d", &num[i]);
	}

	for (int i = 0; i <= n * 3; i++)
	{
		num2[num[i]]++;
		if (num2[num[i]]== 2)printf("%d ", num[i]);
	}



	
	return 0;
}

整数を受け取ったあとに別のfor文で1文字ずつ見ていき受け取った整数の配列num2に１足して2の時にその文字を出力します。

提出したコード内容はほぼ問題ないですが、確保する配列が過剰になってB問で使用した#includeがそのままになってました。

またACを得られなかったコードもここで供養したいと思います。

C問提出TLEコード(誤回答)

#include<stdio.h>
#include<math.h>
int main() {
	static int num[1500000];
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n * 3; i++)
	{
		scanf("%d", &num[i]);
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= n * 3; j++)
		{
			if (num[j] == i)
			{
				num[j] = 0;
				break;
			}
		}
		for (int j = n * 3; j > 0; j--)
		{
			if (num[j] == i)
			{
				num[j] = 0;
				break;
			}
		}
	}

	for (int i = 0; i < n * 3; i++)
	{
		if (num[i])
		{

			printf("%d ", num[i]);
		}
	}
	return 0;
}

このコードでは2重for文を使用して両端から探索し1番目と3番目に出てくる数字に0を代入し、出力時に0以外を出力するものです。
このコードは時間超過のため通りませんでした。
こちらのコードでも配列数が過剰で#includeが残っていますね。

感想

今回のABCは時間内にC問まで解くことができました。
ですが残念ながらUnlatedになってしまいました。

C問では時間超過のコードを出してしまい、改善に少々時間がかかってしまい、なんとか解答を出すことができました。
ですが、これまでに書いたコードではほとんど全探索をしているため、これからは実行時間も気にして書いていきたいと思います。

AtCoder振り返りその1（京セラプログラミングコンテスト2023）

初めに

以前から競技プログラミングのAtCoderには参加しておりました、ブログを書き始めたため今回から振り返りを書いていこうと思います。

今後も可能な限り競技プログラミング参加後、記事を書き、振り返りを行い、提出したコードに満足行っていなかったら都度書き直したいと思います。

A問(A - Water Station)

問題はこちら→A - Water Station

問題内容を読んでみると要は0～100の数字が入力されるのでその数字を5倍数になるよう四捨五入した数字を出力すると書いてあります。

A問提出コード

#include<stdio.h>
 
 
int main(void)
{
	int n;
	
	scanf("%d", &n);
	printf("%d", n / 5 * 5 + ((n % 5 >= 3) ? 5 : 0));
}

出力する際に計算を行っています。
計算内容はn / 5 * 5部分で５の倍数に切り捨てを行い+((n % 5 >= 3) ? 5 : 0)の部分で5で割ったあまりが3以上であれば5を足し、そうでなければ0を足しています。

B問(B - ABCDEFG)

問題はこちら→B - ABCDEFG

直線状にA～Fまでそれぞれの点があり、隣あっているアルファベットの距離のみ説明にあります。
A~F中で２つの異なる点ｑ、点ｐを入力し点ｑと点ｐの距離を出力するものです。

B問提出コード

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


int main(void)
{
	char p,q;
	int a[7] = {0,3,4,8,9,14,23};
	scanf(" %c %c", &p, &q);
	printf("%d", abs(a[p - 'A'] - a[q - 'A']));

	return 0;
}

始めにint aにA点を0とした際の各点のAとの距離を配列に入れます。
点ｑ、点ｐの入力後に、点ｑのＡとの距離-点ｐのＡとの距離をおこないabs関数で絶対値を出しマイナスが出ないよう出力を行います。

かなり簡潔なコードが書けました。直すとしたらaという変数名を使用したとこのみです。

C問(C - Snuke the Cookie Picker)

問題はこちら→C - Snuke the Cookie Picker

長方形で一辺が2～500マスのグリットがありその中に2～500マスの長方形が入っておりその長方形が１マスだけかけているのでそのマスの座標を出力するものです。
グリッドは'.'であらわし中の長方形は'#'です、かけたマスはグリッドと同じ'.'で表します。

C問提出コード

#include<stdio.h>


int main(void)
{
	int h, w;
	char s[501][501] = { 0 };
	scanf("%d %d", &h, &w);
	for (int i = 0; i < h; i++)
	{
		scanf("%s", &s[i]);
	}
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++)
		{

			if (s[i][j] == '.')
			{
				if ((s[((0 <= i || i <= h) ? i: 0) + 1][((0 <= j || j <= h) ? j: 0)] == '#' && s[((0 <= i || i <= h) ? i: 0) - 1] == '#') || (s[((0 <= i || i <= h) ? i: 0) + 1][((0 <= j || j <= h) ? j: 0)] == '#' && s[((0 <= i || i <= h) ? i: 0)][((0 <= j || j <= h) ? j: 0)+1] == '#') || (s[((0 <= i || i <= h) ? i: 0) + 1][((0 <= j || j <= h) ? j: 0)] == '#' && s[((0 <= i || i <= h) ? i: 0)][((0 <= j || j <= h) ? j: 0) - 1] == '#') || (s[((0 <= i || i <= h) ? i: 0)-1][((0 <= j || j <= h) ? j: 0)] == '#' && s[((0 <= i || i <= h) ? i: 0)][((0 <= j || j <= h) ? j: 0) + 1] == '#') || (s[((0 <= i || i <= h) ? i: 0) - 1][((0 <= j || j <= h) ? j: 0)] == '#' && s[((0 <= i || i <= h) ? i: 0)][((0 <= j || j <= h) ? j: 0) - 1] == '#') || (s[((0 <= i || i <= h) ? i: 0)][((0 <= j || j <= h) ? j: 0)+1] == '#' && s[((0 <= i || i <= h) ? i: 0)][((0 <= j || j <= h) ? j: 0) - 1] == '#'))
				{
					printf("%d %d\n", i+1, j+1);
					return 0;
				}
			}
		}
	}
	return 0;
}

一目でわかる見ずらいコードですね。
入力後に二重forループで１マスずつ条件が一致しているか見いき、条件式で見るマスの上下左右のマスに２箇所以上'＃'があった場合との座標を返すものとなっております。

ACと出たのですが見返してみると条件式の中身は左右で1マス以上と上下で1マス以上'＃'があればよくてさらにコードが誤っておりこのままでは範囲外アクセスしてしまいます。

修正したコードがこちらになります。

#include<stdio.h>


int main(void)
{
	int h, w;
	char s[501][501] = { 0 };
	scanf("%d %d", &h, &w);
	for (int i = 0; i < h; i++)
	{
		scanf("%s", &s[i]);
	}
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++)
		{
			if (s[i][j] == '.')
			{
				if ((i + 1 > h ? s[i][j] : s[i + 1][j]) == '#' || (i - 1 < 0 ? s[i][j] : s[i - 1][j]) == '#')
				{
					if ((j + 1 > w ? s[i][j] : s[i][j + 1]) == '#' || (j - 1 < 0 ? s[i][j] : s[i][j - 1]) == '#')
					{
						printf("%d %d\n", i + 1, j + 1);
						return 0;
					}					
				}
			}
		}
	}
	return 0;
}

範囲外アクセスと条件式を書き直し、複数のif分に分けたため見やすくなりました。

感想

今回はＡ問Ｂ問が比較的簡単ですぐに早々に解けて、なおかつ簡潔なコードを書くことができました。
これまで何度かAtCoderに参加しておりましたが、初めてC問を解くことができたので、成長を感じました。

西日本横断サイバーセキュリティ・グランプリに参加しました！

西日本横断サイバーセキュリティ・グランプリ

どうもこんにちはフェルです。

本日6/10行われた「西日本横断サイバーセイキュリティ・グランプリ」に参加してきました。

複数会場がありオンラインでも参加可能とのことだったのでzoomにて参加！

↓イベントの詳細はこちら↓

「西日本横断サイバーセキュリティ・グランプリ」を開催します（四国経済産業局）

登大遊さんによる講演

午前中は登大遊さんによる講演がありました、非常にユニークなスライドを使って非常に興味深く遊び心のあるお話を聞くことができました。

登さん講演で使用されたけしからんスライド

CTF

午後にはクイズや講演、CTFなどを行いました

CTFでは３～４人のチームで行うもので、ヒントがあったり、フラグゲットまでが複雑ではなかったり簡単で初心者でも解きやすい問題でした！

CTFの結果

CTFの結果は２位でした、惜しかったですね。

まとめ

多くの方からサイバーセキュリティのお話が聞くことができて楽しかったです。

また、このようなイベントがあれば参加したいですね。