AtCoder Beginner Contest 322をPythonで解く-Shinoryo's Weblog

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

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 322を, Pythonで解いてみた結果を書き連ねていこうと思います.

1A - First ABC 2
2B - Prefix and Suffix
3C - Festival
4D - Polyomino
5E以降
6参考にしたサイト等

A - First ABC 2

問題文にある条件を愚直に試していくことで実行できます. $i$ 番目から $i + 2$ 番目までの文字を調べるので, $i$ としてループさせるべき数値の範囲に注意してください.

	# 入力
	N = int(input())
	S = input()

	# 「ABC」と連続している部分を探す
	for i in range(N - 2):
	if S[i] == "A" and S[i + 1] == "B" and S[i + 2] == "C":
	print(i + 1)
	exit()

	# 「ABC」と連続している部分がなかった場合
	print(-1)

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

B - Prefix and Suffix

例えば, $S$ が $T$ の接頭辞であることは, 以下をすべて確かめることによって確かめられます.

$S$ の $1$ 文字目が $T$ の $1$ 文字目と一致する.
$S$ の $2$ 文字目が $T$ の $2$ 文字目と一致する.
……
$S$ の $N$ 文字目が $T$ の $N$ 文字目と一致する.

同様に, $S$ が $T$ の接尾辞であることは, 以下をすべて確かめることによって確かめられます.

$S$ の $1$ 文字目が $T$ の $M - N + 1$ 文字目と一致する.
$S$ の $2$ 文字目が $T$ の $M - N + 2$ $文字目と一致する.
……
$S$ の $N$ 文字目が $T$ の $M$ 文字目と一致する.

	# 入力
	N, M = map(int, input().split())
	S = input()
	T = input()

	# 接頭辞かを調べる
	is_prefix = all(S[i] == T[i] for i in range(N))

	# 接尾辞かを調べる
	is_suffix = all(S[i] == T[M - N + i] for i in range(N))

	# 出力
	if is_prefix:
	if is_suffix:
	print(0)
	else:
	print(1)
	else:
	if is_suffix:
	print(2)
	else:
	print(3)

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

C - Festival

最初に $x = 1$ とします. 以下のようにすることで, この問題を解くことができます.

$i$ 日目に対する出力は, $A_{x} - i$ となります. これを出力します.
$i = A_{x}$ ならば, $x$ に $1$ を加えます.

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

	# 今注目するAのインデックス
	now = 0

	# i日目に対してループ
	for i in range(1, N + 1):
	# A[now]がi日目以降に花火が上がる、最も直近の日付となる
	print(A[now] - i)
	# i日目に花火が上がるならば、次のインデックスに移る
	if i == A[now]:
	now += 1

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

あるいは, $i$ 日目に対してそれに近い $A_{j}$ を二分探索する方法でも, (時間計算量はかかりますが)解くことができます.

	import bisect

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

	# i日目に対してループ
	for i in range(1, N + 1):
	print(A[bisect.bisect_left(A, i)] - i)

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

D - Polyomino

$4 \times 4$ のグリッドに対するポリオミノの貼り付け方を全探索すれば, 答えを得ることができます. そのあり得るポリオミノの貼り付け方を全列挙するのが難しいのです.

あるポリオミノの貼り付け方を全列挙したリストを作成するには, 例えば以下のようにします.

あり得る全ての平行移動に対して, ポリオミノが $4 \times 4$ の枠からはみ出ないものをリストに加える.
ポリオミノを90度回転して, 1に戻る.

実際にグリッドにポリオミノを貼り付ける際には, 重ならないように, かつまんべんなく敷き詰められなければならないことに注意してください.

ポリオミノを扱う際は, 外側の空白地帯も含め, $4 \times 4$ の2次元配列のまま扱うとスムーズです.

	# ポリオミノのサイズ
	POLYOMINO_SIZE = 4

	# 1つのポリオミノを受け取る関数
	def input_polyomino():
	return [[piece == "#" for piece in input()] for _ in range(POLYOMINO_SIZE)]

	# あるポリオミノを回転・平行移動して得られるポリオミノのリストを取得する
	# 平行移動した結果、ポリオミノがはみ出てしまう場合は含まない
	def get_possible_polyomino(polyomino):
	possible_polyomino_list = []

	for _ in range(4):
	for offset_x in range(-(POLYOMINO_SIZE - 1), POLYOMINO_SIZE):
	for offset_y in range(-(POLYOMINO_SIZE - 1), POLYOMINO_SIZE):
	if can_shift_polyomino(polyomino, offset_x, offset_y):
	possible_polyomino_list.append(shift_polyomino(polyomino, offset_x, offset_y))
	polyomino = rotate_polyomino(polyomino)

	return possible_polyomino_list

	# あるポリオミノを平行移動した結果、ポリオミノがはみ出なければTrue
	def can_shift_polyomino(polyomino, offset_x, offset_y):
	for i in range(POLYOMINO_SIZE):
	for j in range(POLYOMINO_SIZE):
	if not is_in_POLYOMINO_SIZE(i + offset_x, j + offset_y) and polyomino[i][j]:
	return False
	return True

	# あるポリオミノを平行移動したポリオミノを取得する
	def shift_polyomino(polyomino, offset_x, offset_y):
	shifted_grid = [[False for _ in range(POLYOMINO_SIZE)] for _ in range(POLYOMINO_SIZE)]
	for i in range(POLYOMINO_SIZE):
	for j in range(POLYOMINO_SIZE):
	if is_in_POLYOMINO_SIZE(i + offset_x, j + offset_y):
	shifted_grid[i + offset_x][j + offset_y] = polyomino[i][j]
	return shifted_grid

	# あるポリオミノを90度右回転したポリオミノを取得する
	def rotate_polyomino(polyomino):
	reversed_polyomino = polyomino[::-1]
	return [[j[i] for j in reversed_polyomino] for i in range(POLYOMINO_SIZE)]

	# x, yがポリオミノの範囲に収まっているならばTrue
	def is_in_POLYOMINO_SIZE(x, y):
	return 0 <= x < POLYOMINO_SIZE and 0 <= y < POLYOMINO_SIZE

	# polyomino_1, polyomino_2, polyomino_3によって、グリッドを敷き詰められればTrue
	def can_fill_white_grid(polyomino_1, polyomino_2, polyomino_3):
	for i in range(POLYOMINO_SIZE):
	for j in range(POLYOMINO_SIZE):
	if not(polyomino_1[i][j] or polyomino_2[i][j] or polyomino_3[i][j]):
	return False
	if polyomino_1[i][j] and polyomino_2[i][j]:
	return False
	if polyomino_2[i][j] and polyomino_3[i][j]:
	return False
	if polyomino_3[i][j] and polyomino_1[i][j]:
	return False
	return True

	# 入力
	polyomino_1 = input_polyomino()
	polyomino_2 = input_polyomino()
	polyomino_3 = input_polyomino()

	possible_polyomino_1_list = get_possible_polyomino(polyomino_1)
	possible_polyomino_2_list = get_possible_polyomino(polyomino_2)
	possible_polyomino_3_list = get_possible_polyomino(polyomino_3)

	# 入力したポリオミノを回転・平行移動したポリオミノを重ねて、
	# グリッドに敷き詰めることができるかを調べる
	# 平行移動した結果、ポリオミノがはみ出てしまう場合は含まない
	for possible_polyomino_1 in possible_polyomino_1_list:
	for possible_polyomino_2 in possible_polyomino_2_list:
	for possible_polyomino_3 in possible_polyomino_3_list:
	if can_fill_white_grid(possible_polyomino_1, possible_polyomino_2, possible_polyomino_3):
	print("Yes")
	exit()
	print("No")

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

E以降

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

参考にしたサイト等

「解説 - AtCoder Beginner Contest 322」
404 Not Found - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
Wakasugi Tatsuroh様による「Pythonで二分探索を行うライブラリ『bisect』」
Pythonで二分探索を行うライブラリ「bisect」 - Qiita
趣味で競プロをやるようになり, Atcoderの問題を何問か解いているのだが, やっている内に覚えないといけないこともいくつかあるわけで. その内の一つに二分探索というアルゴリズムを使うという場面を多…

AtCoder Beginner Contest 322をPythonで解く

A - First ABC 2

B - Prefix and Suffix

C - Festival

D - Polyomino

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