ユニークビジョンプログラミングコンテスト2023 春 (AtCoder Beginner Contest 300)をPythonで解く-Shinoryo's Weblog

Daniel AgreloによるPixabay(https://pixabay.com/)からの画像

こんにちは, Shinoryoです.

今回はユニークビジョンプログラミングコンテスト2023 春 (AtCoder Beginner Contest 300)を, Pythonで解いてみた結果を書き連ねていこうと思います.

1A - N-choice question
2B - Same Map in the RPG World
3C - Cross
4D - AABCC
5E以降
6参考にしたサイト等

A - N-choice question

$A + B$ を求めて, $C$ の中にそれと一致するものが存在するかを調べればよいです. for文を用いて次のように実装できます.

	# 入力
	N, A, B = list(map(int, input().split()))
	C = list(map(int, input().split()))

	# C内を検索し、出力
	A_plus_B = A + B
	for i in range(N):
	if C[i] == A_plus_B:
	print(i + 1)
	exit()

view raw atcoder-abc-300-a.py hosted with ❤ by GitHub

あるいは, リストのメソッド.index()を用いて, リストの要素のインデックスを取得することもできます. インデックスと選択肢の番号は $1$ ずれていることに注意してください.

	# 入力
	N, A, B = list(map(int, input().split()))
	C = list(map(int, input().split()))

	# C内を検索し、出力
	print(C.index(A + B) + 1)

view raw atcoder-abc-300-a-2.py hosted with ❤ by GitHub

B - Same Map in the RPG World

「 $s$ 回縦方向シフトしたあとの $A$ 」と「 $s + H$ 回縦方向シフトしたあとの $A$ 」が一致することや, 「 $t$ 回横方向シフトしたあとの $A$ 」と「 $t + W$ 回横方向シフトしたあとの $A$ 」が一致することから, $H$ 回以上の縦方向シフトや, $W$ 回以上の横方向シフトを考える必要はありません. 純粋に全シフトパターンを確かめても, 少ない計算量で済みます.

numpyのnp.roll()を用いれば, 配列をシフトさせたものを簡単に取得することができます.

	import numpy as np

	# 入力
	H, W = list(map(int, input().split()))
	A = []
	for _ in range(H):
	A.append(list(input()))
	B = []
	for _ in range(H):
	B.append(list(input()))
	A = np.array(A)
	B = np.array(B)

	# いくつずらしたら一致するかを調べていく
	# 縦方向のシフトs回、横方向のシフトt回を行い、一致を調査する
	for s in range(H):
	for t in range(W):
	if (A == B).all():
	print("Yes")
	exit()
	A = np.roll(A, 1, axis=1)
	A = np.roll(A, 1, axis=0)
	print("No")

view raw atcoder-abc-300-b.py hosted with ❤ by GitHub

あるいは, numpyを用いずに, 配列のシフトを実装しても良いです.

	# 2次元配列を縦方向に1ずらす関数
	def vertical_shift(array2D, H, W):
	array2D_shifted = [[None for _ in range(W)] for _ in range(H)]
	for i in range(H):
	for j in range(W):
	array2D_shifted[(i + 1) % H][j] = array2D[i][j]
	return array2D_shifted

	# 2次元配列を横方向に1ずらす関数
	def horizontal_shift(array2D, H, W):
	array2D_shifted = [[None for _ in range(W)] for _ in range(H)]
	for i in range(H):
	for j in range(W):
	array2D_shifted[i][(j + 1) % W] = array2D[i][j]
	return array2D_shifted

	# 入力
	H, W = list(map(int, input().split()))
	A = []
	for _ in range(H):
	A.append(list(input()))
	B = []
	for _ in range(H):
	B.append(list(input()))

	# いくつずらしたら一致するかを調べていく
	# 縦方向のシフトs回、横方向のシフトt回を行い、一致を調査する
	for s in range(H):
	for t in range(W):
	ok = True
	for i in range(H):
	for j in range(W):
	if A[i][j] != B[i][j]:
	ok = False
	if ok:
	print("Yes")
	exit()
	A = horizontal_shift(A, H, W)
	A = vertical_shift(A, H, W)
	print("No")

view raw atcoder-abc-300-b-2.py hosted with ❤ by GitHub

さらに, 配列のシフトを実装するのではなく, $A$ と $B$ が一致しているかを調べるところで, $A$ の要素のインデックスをずらしていくだけで十分です. $s$ 回縦方向シフトして $t$ 回横方向シフトした $A$ と $B$ を比べるときは, A[(i + s) % H][(j + t) % W]とB[i][j]を比較すればよいのです.

	# 入力
	H, W = list(map(int, input().split()))
	A = []
	for _ in range(H):
	A.append(list(input()))
	B = []
	for _ in range(H):
	B.append(list(input()))

	# いくつずらしたら一致するかを調べていく
	# 縦方向のシフトs回、横方向のシフトt回を行い、一致を調査する
	for s in range(H):
	for t in range(W):
	ok = True
	for i in range(H):
	for j in range(W):
	if A[(i + s) % H][(j + t) % W] != B[i][j]:
	ok = False
	if ok:
	print("Yes")
	exit()
	print("No")

view raw atcoder-abc-300-b-3.py hosted with ❤ by GitHub

C - Cross

一つひとつの#マスに対して, その周囲のマスが#であるかどうかを愚直に調べていくことで, 解くことができます.

	# 入力
	H, W = list(map(int, input().split()))
	C = []
	for _ in range(H):
	C.append(list(input()))
	N = min(H, W)

	# バツ印のサイズを格納していく
	# index 0、1は使わない
	ans = [0 for _ in range(N + 2)]

	# バツ印調査
	for i in range(1, H - 1):
	for j in range(1, W - 1):
	for level in range(N):
	if i - level >= 0 and i + level < H and j - level >= 0 and j + level < W:
	if C[i - level][j - level] != "#" or C[i + level][j - level] != "#" or C[i - level][j + level] != "#" or C[i + level][j + level] != "#":
	ans[level] += 1
	break
	else:
	ans[level] += 1
	break

	# 出力
	print(" ".join(list(map(str, ans[2:]))))

view raw atcoder-abc-300-c.py hosted with ❤ by GitHub

あるいは, #マスがバツ印以外には使われていないことを利用して, #が何マス連結しているかを調べていくことでも, この問題を解くことができます.

例えば, Union Findを用いて実装することができます. 最初は1つひとつバラバラな要素が用意されます. そして, 「2つのまとまりをつなげる」という操作を繰り返し, 最終的にある要素がどの集合に属しているかを管理していくアルゴリズムです.

Union Findは, AtCoder Beginner Contest 214をPythonで解くのD - Sum of Maximum Weightsでも登場しています.

	# Union Findクラス
	class UnionFind:
	def __init__(self, n):
	# parentは各要素の親要素の番号を格納するリスト
	# 初期状態では、各要素の親要素は自分自身として初期化する
	self.parent = [i for i in range(n)]
	# group_sizeは各グループのサイズ（要素数）を格納するリスト
	# 初期状態では、各要素が自分自身を含むサイズ1のグループを形成している
	self.group_size = [1] * n

	def find(self, x):
	# xが属するグループの根を返す
	if self.parent[x] == x:
	return x
	else:
	# 経路圧縮(xが属するグループの親を根に変更する)
	self.parent[x] = self.find(self.parent[x])
	return self.parent[x]

	def union(self, x, y):
	# xとyが属するグループを併合する
	px, py = self.find(x), self.find(y)
	if px == py:
	# すでに同じグループに属している場合は何もしない
	return
	elif self.group_size[px] < self.group_size[py]:
	# グループのサイズが小さい方の根を大きい方の根に繋げる
	self.parent[px] = py
	self.group_size[py] += self.group_size[px]
	else:
	self.parent[py] = px
	self.group_size[px] += self.group_size[py]

	def size(self, x):
	# xが属するグループのサイズ（要素数）を返す
	return self.group_size[self.find(x)]

	def same(self, x, y):
	# xとyが同じグループに属するかどうかを返す
	return self.find(x) == self.find(y)

	def members(self, x):
	# xが属するグループに属する要素をリストで返す
	root = self.find(x)
	return [i for i in range(len(self.parent)) if self.find(i) == root]

	def roots(self):
	# すべての根の要素をリストで返す
	return [i for i, x in enumerate(self.parent) if i == x]

	def group_count(self):
	# グループの数を返す
	return len(self.roots())

	# 入力
	H, W = list(map(int, input().split()))
	C = []
	for _ in range(H):
	C.append(list(input()))
	N = min(H, W)

	# バツ印調査
	# バツ印を構成しているマス同士をUnion Findでつなげる
	uf = UnionFind(H * W)
	for i in range(H):
	for j in range(W):
	if C[i][j] == "#":
	if i - 1 >= 0 and j - 1 >= 0 and C[i - 1][j - 1] == "#":
	uf.union(i * W + j, (i - 1) * W + (j - 1))
	if i - 1 >= 0 and j + 1 < W and C[i - 1][j + 1] == "#":
	uf.union(i * W + j, (i - 1) * W + (j + 1))
	if i + 1 < H and j - 1 >= 0 and C[i + 1][j - 1] == "#":
	uf.union(i * W + j, (i + 1) * W + (j - 1))
	if i + 1 < H and j + 1 < W and C[i + 1][j + 1] == "#":
	uf.union(i * W + j, (i + 1) * W + (j + 1))

	# バツ印のサイズを格納していく
	# index 0、1は使わない
	ans = [0 for _ in range(N + 1)]

	# Union Findの根に対して、その要素数を取得する
	# (要素数 - 1) / 4が、バツ印のサイズに対応する
	for root in uf.roots():
	ans[(uf.size(root) - 1) // 4] += 1

	# 出力
	print(" ".join(list(map(str, ans[1:]))))

view raw atcoder-abc-300-c-2.py hosted with ❤ by GitHub

D - AABCC

$N \leq 10^{12}$ であるので, $c$ の最大値は

\begin{aligned} (1) & 2^{2} \times 3 \times c^{2} & = 10^{12} \end{aligned}

を解いて $c = 288675$ と得られます. ゆえに, $a$ , $b$ , $c$ の取りうる数の一覧表として, まず $288675$ までの素数のリストを取得する必要があります. これはEratosthenesの篩を用いることで得ることができます. Eratosthenesの篩は数学などでよく知られた手法ですが, 例えば以下のサイトをご覧ください(外部).

Pythonでは例えば以下のように実装できます. 整数 $n$ を与えると, その整数以下の素数のリストを返す関数です.

	def eratosthenes(n):
	"""
	Python function to get a list of prime numbers less than or equal to n using the Sieve of Eratosthenes

	Args:
	n (int)

	Returns:
	(list; int): a list of prime numbers
	"""
	sosu_check = [True for _ in range(n + 1)]
	sosu_check[0] = False
	sosu_check[1] = False
	for i in range(2, int(n**0.5) + 1):
	if sosu_check[i]:
	for j in range(i * i, n + 1, i):
	sosu_check[j] = False
	return [i for i in range(n + 1) if sosu_check[i]]

view raw eratosthenes.py hosted with ❤ by GitHub

後は, $a = 2$ , $b = 3$ , $c = 5$ から順番に, 問題文の条件に適している個数をカウントしていくだけです. 三重ループになりますが, ループの途中で適切にbreakを挟むことで, TLEにならずにACすることができます. 公式解説では一番深いところのbreakだけで済むという記述がありますが, Pythonではおそらく全てのループで適切なbreakを挟まないとTLEになります(間違えていたら申し訳ございません).

	# 入力
	N = int(input())

	# 288675以内の素数のリストを取得
	def eratosthenes(n):
	"""
	Python function to get a list of prime numbers less than or equal to n using the Sieve of Eratosthenes

	Args:
	n (int)

	Returns:
	(list; int): a list of prime numbers
	"""
	sosu_check = [True for _ in range(n + 1)]
	sosu_check[0] = False
	sosu_check[1] = False
	for i in range(2, int(n**0.5) + 1):
	if sosu_check[i]:
	for j in range(i * i, n + 1, i):
	sosu_check[j] = False
	return [i for i in range(n + 1) if sosu_check[i]]
	sosu_list = eratosthenes(288675)
	sosu_list_len = len(sosu_list)

	# 問題文の条件に適している個数をカウントし、出力
	count = 0
	for i in range(sosu_list_len - 2):
	# S_i^2 * S_(i + 1) * S_(i + 2)^2の時点でNを超えていたらbreak
	if sosu_list[i] * sosu_list[i] * sosu_list[i + 1] * sosu_list[i + 2] * sosu_list[i + 2] > N:
	break
	for j in range(i + 1, sosu_list_len - 1):
	# S_i^2 * S_j * S_(j + 1)^2の時点でNを超えていたらbreak
	if sosu_list[i] * sosu_list[i] * sosu_list[j] * sosu_list[j + 1] * sosu_list[j + 1] > N:
	break
	for k in range(j + 1, sosu_list_len):
	# S_i^2 * S_j * S_k^2がN以下であればカウント、Nを超えたらbreak
	if sosu_list[i] * sosu_list[i] * sosu_list[j] * sosu_list[k] * sosu_list[k] <= N:
	count += 1
	else:
	break
	print(count)

view raw atcoder-abc-300-d.py hosted with ❤ by GitHub

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等

「解説 - ユニークビジョンプログラミングコンテスト2023 春 (AtCoder Beginner Contest 300)」
Editorial - ユニークビジョンプログラミングコンテスト2023 春 (AtCoder Beginner Contest 300)
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
nkmk様による「Pythonのリストの要素のインデックス（何番目か）を取得」
Pythonのリストの要素のインデックス（何番目か）を取得 | note.nkmk.me
Pythonのリスト（配列）の要素のインデックス, つまりその要素が何番目に格納されているかを取得する方法について, 以下の内容を説明する. リストの要素が重複していない場合: index() リストの要素が重複している場合: index(), enumerate(), リスト内包表記タプルのインデックスを取得最大値・最小値のインデックス（位...
nkmk様による「NumPy配列ndarrayをシフト（スクロール）させるnp.roll」
NumPy配列ndarrayをシフト（スクロール）させるnp.roll | note.nkmk.me
NumPyの関数np.roll()を使うとNumPy配列ndarrayをシフト（スクロール）させることができる. 配列の開始位置をずらすときなどに使う. numpy.roll — NumPy v1.16 Manual ここでは以下の内容について説明する. np.roll()の基本的な使い方二次元配列（多次元配列）の場合画像処理への応用（画像をスクロール）一次元配列を...
nkmk様による「PythonでのUnion-Find（素集合データ構造）の実装と使い方」
PythonでのUnion-Find（素集合データ構造）の実装と使い方 | note.nkmk.me
PythonでのUnion Findデータ構造（素集合データ構造）の実装とその使い方を説明する. まずはじめに最終形のクラスとその使い方のサンプルコードを示し, 後半で素朴な実装からいくつかの工夫を加えて最終形に至るまでを説明する. Union Find（素集合データ構造）の概要 PythonでのUnion Findの実装例サンプルコードのクラス...

ユニークビジョンプログラミングコンテスト2023 春 (AtCoder Beginner Contest 300)をPythonで解く

A - N-choice question

B - Same Map in the RPG World

C - Cross

D - AABCC

E以降

参考にしたサイト等

0 件のコメント:

コメントを投稿 (Please feel free to ask me about your questions! You can use Japanese or English in the comments.)

Search

About Me

Labels

Blog Archives

Twitter