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

/* -----codeの行番号----- */