東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 307）をPythonで解く-Shinoryo's Weblog

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

こんにちは, Shinoryoです.

今回は東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 307）を, Pythonで解いてみた結果を書き連ねていこうと思います.

1A - Weekly Records
2B - racecar
3C - Ideal Sheet
4D - Mismatched Parentheses
5E以降
6参考にしたサイト等

A - Weekly Records

組み込み関数sum()を用いて計算することができます.

	N = int(input())
	A = list(map(int, input().split()))
	print(" ".join([str(sum(A[7i:7(i + 1)])) for i in range(N)]))

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

B - racecar

「 $S_{1}$ ～ $S_{N}$ から2個( $S_{i}$ , $S_{j}$ )選んで並べる順列」の全てに対してループさせて, それぞれで $S_{i}$ と $S_{j}$ をこの順に連結した文字列が回文となるかを調べればよいです. そのような順列を順番に取り出していくのには, itertools.permutationを使うと便利です.

	import itertools

	# 入力
	N = int(input())
	S = [input() for _ in range(N)]

	# 「S_1～S_Nから2個選んで並べる順列」の全てに対してループ
	for S_i, S_j in itertools.permutations(S, 2):
	test_string = S_i + S_j
	len_test_string = len(test_string)

	isKaibun = True
	for k in range(len_test_string):
	if test_string[k] != test_string[len_test_string - 1 - k]:
	isKaibun = False

	if isKaibun:
	print("Yes")
	exit()

	# 回文を作れなかった場合はNo
	print("No")

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

C - Ideal Sheet

ここでは, シート $X$ を切り出す範囲をあらかじめ決めておくことにします. 具体的には, シート $C$ の座標 $(0, 0)$ から $(H_{X} - 1, W_{X} - 1)$ の範囲を切り出すことにします. この切り出す範囲に対して, シート $A$ とシート $B$ をどのように配置するかを考えるのです.

高橋君が目標を達成できるシート $A$ とシート $B$ の配置は, 以下の3つの条件をすべて満たせばよいことが分かります.

シート $X$ の範囲に, シート $A$ に存在する黒いマスが全て存在する.
シート $X$ の範囲に, シート $B$ に存在する黒いマスが全て存在する.
シート $X$ の範囲の黒いマスが, 理想とするシート $X$ の黒いマスと一致する.

シート自体は大きくないので, これを愚直に実装すればACとなります. CPython 3.11.4だと, 適切にbreakしないとTLEになる場合があります.

	import itertools

	# 入力
	H_A, W_A = map(int, input().split())
	A = [list(input()) for _ in range(H_A)]
	H_B, W_B = map(int, input().split())
	B = [list(input()) for _ in range(H_B)]
	H_X, W_X = map(int, input().split())
	X = [list(input()) for _ in range(H_X)]

	# Xの範囲にAとBを重ねる方法の数だけループ
	for i_A, j_A, i_B, j_B in itertools.product(range(- H_A + 1, H_X), range(- W_A + 1, W_X), range(- H_B + 1, H_X), range(- W_B + 1, W_X)):
	# 条件1：Xの範囲にAに存在する黒いマスが全て存在する
	cond1 = True
	for k_A, l_A in itertools.product(range(H_A), range(W_A)):
	if 0 <= (i_A + k_A) < H_X and 0 <= (j_A + l_A) < W_X:
	continue
	elif A[k_A][l_A] == "#":
	cond1 = False
	break
	# 条件1が満たされなければcontinue
	if not(cond1):
	continue

	# 条件2：Xの範囲にBに存在する黒いマスが全て存在する
	cond2 = True
	for k_B, l_B in itertools.product(range(H_B), range(W_B)):
	if 0 <= (i_B + k_B) < H_X and 0 <= (j_B + l_B) < W_X:
	continue
	elif B[k_B][l_B] == "#":
	cond2 = False
	break
	# 条件2が満たされなければcontinue
	if not(cond2):
	continue

	# 条件3：Xの範囲の黒いマスが理想とするシートXの黒いマスと一致する
	cond3 = True
	for k_X, l_X in itertools.product(range(H_X), range(W_X)):
	cond3_A_is_Hash = (0 <= k_X - i_A < H_A) and (0 <= l_X - j_A < W_A) and (A[k_X - i_A][l_X - j_A] == "#")
	cond3_B_is_Hash = (0 <= k_X - i_B < H_B) and (0 <= l_X - j_B < W_B) and (B[k_X - i_B][l_X - j_B] == "#")
	if X[k_X][l_X] == "#":
	if not (cond3_A_is_Hash or cond3_B_is_Hash):
	cond3 = False
	break
	else:
	if cond3_A_is_Hash or cond3_B_is_Hash:
	cond3 = False
	break
	# 条件3が満たされなければcontinue
	if not(cond3):
	continue

	# 条件1、条件2、条件3がすべて満たされれば、Yesとなる
	print("Yes")
	exit()

	# 条件1、条件2、条件3の全てを満たせなかったら、Noとなる
	print("No")

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

あるいは, シート $X$ に余計な黒いマスがあっては条件を満たせないことから, 上記の条件は次のように書き換えられます.

シート $A$ の黒いマスは, 理想とするシート $X$ の黒いマスに含まれる.
シート $B$ の黒いマスは, 理想とするシート $X$ の黒いマスに含まれる.
理想とするシート $X$ の黒いマスは, シート $A$ またはシート $B$ の黒いマスに含まれる.

黒いマスの位置をキャッシュしておくことで, さらに高速にこの問題を解くことができます.

	import itertools

	# 入力
	H_A, W_A = map(int, input().split())
	A = [list(input()) for _ in range(H_A)]
	H_B, W_B = map(int, input().split())
	B = [list(input()) for _ in range(H_B)]
	H_X, W_X = map(int, input().split())
	X = [list(input()) for _ in range(H_X)]

	# 黒いマスの位置をキャッシュ
	black_cells_A = {(i, j) for i in range(H_A) for j in range(W_A) if A[i][j] == "#"}
	black_cells_B = {(i, j) for i in range(H_B) for j in range(W_B) if B[i][j] == "#"}
	black_cells_X = {(i, j) for i in range(H_X) for j in range(W_X) if X[i][j] == "#"}

	# Xの範囲にAとBを重ねる方法の数だけループ
	for i_A, j_A, i_B, j_B in itertools.product(range(- H_A + 1, H_X), range(- W_A + 1, W_X), range(- H_B + 1, H_X), range(- W_B + 1, W_X)):
	# 条件1：Xの範囲にAに存在する黒いマスが全て存在する
	# → Aの黒いマスは全てXの黒いマスである
	cond1 = True
	for (k_A, l_A) in black_cells_A:
	if ((i_A + k_A), (j_A + l_A)) not in black_cells_X:
	cond1 = False
	break
	# 条件1が満たされなければcontinue
	if not(cond1):
	continue

	# 条件2：Xの範囲にBに存在する黒いマスが全て存在する
	# → Bの黒いマスは全てXの黒いマスである
	cond2 = True
	for (k_B, l_B) in black_cells_B:
	if ((i_B + k_B), (j_B + l_B)) not in black_cells_X:
	cond2 = False
	break
	# 条件2が満たされなければcontinue
	if not(cond2):
	continue

	# 条件3：Xの範囲の黒いマスが与えられるものと一致する
	# → Xの黒いマスは全て、Aの黒いマスまたはBの黒いマスである
	cond3 = True
	for (k_X, l_X) in black_cells_X:
	cond3_A_is_Hash = ((k_X - i_A, l_X - j_A) in black_cells_A)
	cond3_B_is_Hash = ((k_X - i_B, l_X - j_B) in black_cells_B)
	if not (cond3_A_is_Hash or cond3_B_is_Hash):
	cond3 = False
	break
	# 条件3が満たされなければcontinue
	if not(cond3):
	continue

	# 条件1、条件2、条件3がすべて満たされれば、Yesとなる
	print("Yes")
	exit()

	# 条件1、条件2、条件3の全てを満たせなかったら、Noとなる
	print("No")

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

なお, 上記のコードでは, 多重ループの記述に多重ループitertools.product()を使用しています.

D - Mismatched Parentheses

解説にもあるように, 「先頭から順に見て, )を見つけるたびに, 直前の(までを削除する」を実行すればよいです. 直前の「(」を覚えておくスタックや, 出力する文字列を記録しておくスタックは, Pythonではcollectionsモジュールのdeque型を用いれば簡単に実装できます.

	from collections import deque

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

	# 答えを格納するスタック
	ans = deque([])

	# ans中の"("の位置を記録しておくスタック
	kakko_left_index = deque([])

	# Sの要素を順番にループ
	for i in range(N):
	ans.append(S[i])

	# "("ならば、「ans上のインデックス」をkakko_left_indexに記録する
	if S[i] == "(":
	kakko_left_index.append(len(ans) - 1)
	# ")"であり、まだ出てきて何もしていない"("が存在すれば、()で囲まれた範囲をansから削除する
	elif S[i] == ")" and len(kakko_left_index) > 0:
	for _ in range(kakko_left_index.pop(), len(ans)):
	ans.pop()

	# 出力
	print("".join(ans))

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

E以降

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

参考にしたサイト等

「解説 - 東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 307）」
Editorial - Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 307)
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ではmathモジュールを使って階乗や順列・組み合わせの総数を算出できる. SciPyでも順列・組み合わせの総数を算出する関数が提供されている. また, itertoolsモジュールを使ってリストなどから順列・組み合わせを生成して列挙することも可能. 階乗: math.factorial() 順列の総数を算出math.perm()scipy.special.perm()...
nkmk様による「Pythonのfor文によるループ処理（range, enumerate, zipなど）」
Pythonのfor文によるループ処理（range, enumerate, zipなど） | note.nkmk.me
Pythonのfor文によるループ処理（繰り返し処理）について説明する. 基本的な文法と, for文とrange()やenumerate(), zip()などを組み合わせて使う例を紹介する. 8. 複合文 (compound statement) - for文 — Python 3.11.3 ドキュメント Pythonのfor文の基本的な書き方: for ... in ... :Pythonのfor文は他言語のforeach文と...
nkmk様による「Pythonのdequeでキュー, スタック, デック（両端キュー）を扱う」
Pythonのdequeでキュー, スタック, デック（両端キュー）を扱う | note.nkmk.me
Pythonの標準ライブラリcollectionsモジュールのdeque型を使うと, データをキューやスタック , デック（両端キュー）として効率的に扱うことができる. collections.deque --- コンテナデータ型 — Python 3.11.4 ドキュメント組み込みのリストlistをキューやスタック, デック（両端キュー）として使うことも可能だが, リス...

東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 307）をPythonで解く

A - Weekly Records

B - racecar

C - Ideal Sheet

D - Mismatched Parentheses

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