トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）をPythonで解く-Shinoryo's Weblog

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

こんにちは, Shinoryoです.

今回はトヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）を, Pythonで解いてみた結果を書き連ねていこうと思います.

1A - Spoiler
- 1.1|の位置を探して求める
- 1.2正規表現を用いる
2B - Delimiter
3C - A+B+C
4D - String Bags
5E - Insert or Erase
6F以降
7参考にしたサイト等

A - Spoiler

`|`の位置を探して求める

1つ目の|の位置 $i$ と2つ目の|の位置 $j$ を求めます. 文字列 $S$ の $i$ 文字目より前と $j$ 文字目より後を連結したものを出力すればよいです.

	# 入力
	S = input()

	# 1つ目の\|と2つ目の\|を見つける
	first = S.find("\|")
	second = S.rfind("\|")

	# 出力
	print(S[:first] + S[second + 1:])

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

正規表現を用いる

正規表現を用いて, 「|と|で囲まれた文字列」を空白で置換します.

	import re

	print(re.sub("\\|.*\\|", "", input()))

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

B - Delimiter

$A_{i}$ を順番に読み込み, 記憶していきます. $0$ が入力されたら, 記憶していたそれまでの入力を逆順に出力すればよいです. $A_{N} = 0$ であることが保証されていることに注意してください.

	input_list = []

	while True:
	# 入力をinput_listに格納する
	input_i = int(input())
	input_list.append(input_i)

	# 0が入力されたら、それまでの入力を逆順に出力する
	if input_i == 0:
	for i in range(len(input_list) - 1, -1, -1):
	print(input_list[i])
	break

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

C - A+B+C

$A$ , $B$ , $C$ から1つずつ要素を選んで和を取ることによって得られる数字の全パターンを計算しておきます. これに $X_{i}$ が含まれているかによって, Yesを出力するかNoを出力するかを判定します.

全パターン計算に $O (N M L)$ , 各問題を解くのに $O (1)$ , 合計で $O (N M L + Q)$ でこの問題を解くことができます.

	import itertools

	# 入力
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	l = int(input())
	c = list(map(int, input().split()))
	q = int(input())
	x = list(map(int, input().split()))

	# A、B、Cから1つずつ要素を選んで和を求める
	# その結果の全パターンを集合として記録する
	all_sum_pattern = set()
	for a_i, b_i, c_i in itertools.product(a, b, c):
	all_sum_pattern.add(a_i + b_i + c_i)

	# 和をx_iにすることができるかは、x_iがall_sum_patternに含まれるかで判断できる
	for i in range(q):
	if x[i] in all_sum_pattern:
	print("Yes")
	else:
	print("No")

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

D - String Bags

次の2次元配列を順に埋めていく動的計画法によって, この問題を解くことができます.

dp[i][j]: $i$ 個目の袋まで処理した結果, $T$ の最初から $j$ 文字目まで一致させるのにかかる最小金額

$i$ 個目の袋まで処理した結果, $T$ の最初から $j$ 文字目まで一致させることができたとします. このとき, 次のようにdpを更新していきます.

$i + 1$ 個目の袋から何も取り出さなかった場合, dp[i + 1][j] = dp[i][j].
$i + 1$ 個目の袋から文字列 $x$ を取り出し, $T$ の最初から $j + len (x)$ 文字目まで一致させることできた場合, dp[i + 1][j + len(x)] = dp[i][j] + 1.

最終的に, dp[N][len(T)]を出力します.

	# 入力
	T = input()
	N = int(input())
	S = []
	for _ in range(N):
	input_line = input().split()
	S.append(input_line[1:])

	# 動的計画法
	# dp[i][j]: i個目の袋まで処理した結果、Tの最初からj文字目まで一致させるのにかかる最小金額
	dp = [[float("inf") for _ in range(len(T) + 1)] for _ in range(N + 1)]

	# 最初にかかる金額は0
	dp[0][0] = 0

	for i in range(N):
	# 袋を処理しなかった場合の金額を計算する
	for j in range(len(T) + 1):
	dp[i + 1][j] = dp[i][j]

	for x in S[i]:
	for j in range(len(T) - len(x) + 1):
	if T[j: j + len(x)] != x:
	continue
	# 文字列がj + 1文字目からj + len(x)文字目までが一致すれば、連結成功
	# 最小金額を更新する
	dp[i + 1][j + len(x)] = min(dp[i + 1][j + len(x)], dp[i][j] + 1)

	# 最小金額が無限の場合は、どのようにしても最終的なSをTに一致させられない場合
	if dp[N][len(T)] == float("inf"):
	print(-1)
	else:
	print(dp[N][len(T)])

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

本ブログでも, 過去に以下のような動的計画法を用いる問題を取り扱っています.

E - Insert or Erase

リストに対する挿入・削除を素早く行うには, 双方向連結リスト(doubly-linked list)というデータ構造を用いるのが良いです. 各ノードが1つ前・1つ後のノードへの参照を有します.

Lasindi, Public domain, via Wikimedia Commons

実際, 挿入・削除を行うには, 関係するノードのデータを変更するだけでよいです.

Singly_linked_list_insert_after.png: Derrick Coetzeederivative work: Pluke, Public domain, via Wikimedia Commons

Pluke, Public domain, via Wikimedia Commons

典型的な双方向連結リストの場合, ある値に対応するノードを探すには, リストの先頭からノードをたどっていく必要があります. そのため, ある値に対応するノードを効率的に探す手法を用意することで, 計算時間を短縮する必要があります. Pythonでは辞書(dict型)を用いることができます.

	from enum import Enum, auto
	from typing import List

	class IntLinkedListException(Exception):
	"""
	双方向連結リストを表すクラス用の例外クラス。
	"""
	pass

	class IntLinkedList:
	"""
	双方向連結リストを表すクラス。
	"""

	class Dummy(Enum):
	HEAD = auto()
	TAIL = auto()

	def __init__(self) -> None:
	"""
	先頭と末尾のダミー要素を持つように初期化する。
	"""
	self.before = {}
	self.after = {}

	self.after[self.Dummy.HEAD] = self.Dummy.TAIL
	self.before[self.Dummy.TAIL] = self.Dummy.HEAD

	def append(self, item: int, previous_item: int = Dummy.HEAD) -> None:
	"""
	アイテムを追加する。
	すでに存在するアイテムを指定してはならない。

	Args:
	item (int): 追加するアイテム。
	previous_item (int, optional): この後にitemを追加する。デフォルトは先頭のダミー要素。
	Raises:
	IntLinkedListException: itemがこのリストに存在する場合。
	"""
	if item in self.before.keys():
	raise IntLinkedListException("{}はこのリストに存在するため、追加できません。".format(item))
	if previous_item not in self.after.keys():
	raise IntLinkedListException("{}はこのリストに存在しないため、アイテムを追加できません。".format(previous_item))

	self.before[item] = previous_item
	self.after[item] = self.after[previous_item]
	self.before[self.after[previous_item]] = item
	self.after[previous_item] = item

	def append_left(self, item: int, next_item: int = Dummy.TAIL) -> None:
	"""
	アイテムを追加する。

	Args:
	item (int): 追加するアイテム。
	next_item (int, optional): この前にアイテムを追加する。デフォルトは末尾のダミー要素。
	"""
	if item in self.after.keys():
	raise IntLinkedListException("{}はこのリストに存在するため、追加できません。".format(item))
	if next_item not in self.before.keys():
	raise IntLinkedListException("{}はこのリストに存在しないため、アイテムを追加できません。".format(next_item))

	self.after[item] = next_item
	self.before[item] = self.before[next_item]
	self.after[self.before[item]] = item
	self.before[next_item] = item

	def remove(self, item: int):
	"""
	リストからアイテムを削除する。

	Args:
	item (int): 削除するアイテム。
	Raises:
	IntLinkedListException: Dummy.HEADかDummy.TAILが指定された場合、または、itemがこのリストに存在しない場合。
	"""
	if item in {self.Dummy.HEAD, self.Dummy.TAIL}:
	raise IntLinkedListException("{}は削除できません。".format(item))
	if item not in self.after.keys():
	raise IntLinkedListException("{}はこのリストに存在しないため、削除できません。".format(item))

	self.after[self.before[item]] = self.after[item]
	self.before[self.after[item]] = self.before[item]
	del self.before[item]
	del self.after[item]

	def to_list(self) -> List[int]:
	"""
	リストをPythonのリストに変換する。

	Returns:
	List[int]: リストのアイテムを含むPythonのリスト。
	"""
	data_list = []
	current = self.after[self.Dummy.HEAD]
	while current != self.Dummy.TAIL:
	data_list.append(current)
	current = self.after[current]
	return data_list

	# 入力
	n = int(input())
	a = list(map(int, input().split()))

	# 双方向リストを作成する
	a_linked_list = IntLinkedList()
	for a_i in a:
	a_linked_list.append_left(a_i)

	# クエリを実行する
	for _ in range(int(input())):
	query = list(map(int, input().split()))
	if query[0] == 1:
	a_linked_list.append(query[2], query[1])
	else:
	a_linked_list.remove(query[1])

	# 出力
	print(*a_linked_list.to_list())

view raw atcoder-abc-344-e.py hosted with ❤ by GitHub

私用したIntLinkedListは, GitHubにも投稿してあります.

F以降

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

参考にしたサイト等

「解説 - トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）」
Editorial - Toyota Programming Contest 2024#3（AtCoder Beginner Contest 344）
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
nkmk様による「Pythonの正規表現モジュールreの使い方（match, search, subなど）」
Pythonの正規表現モジュールreの使い方（match, search, subなど） | note.nkmk.me
Pythonで正規表現の処理を行うには標準ライブラリのreモジュールを使う. 正規表現パターンによる文字列の抽出や置換, 分割などができる. re --- 正規表現操作 — Python 3.11.3 ドキュメント正規表現 HOWTO — Pyt ...
「連結リスト - Wikipedia」
連結リスト - Wikipedia
No description
nkmk様による「Pythonで辞書を作成するdict()と波括弧, 辞書内包表記」
Pythonで辞書を作成するdict()と波括弧, 辞書内包表記 | note.nkmk.me
Pythonで辞書（dict型オブジェクト）を作成するには様々な方法がある. キーkeyと値valueを一つずつ設定するだけでなく, リストから辞書を作成することも可能. 波括弧{}で辞書を作成キーと値を個別に指定複数の辞書 ...

トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）をPythonで解く

A - Spoiler

`|`の位置を探して求める

正規表現を用いる

B - Delimiter

C - A+B+C

D - String Bags

E - Insert or Erase

F以降

参考にしたサイト等

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

トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）をPythonで解く

A - Spoiler

|の位置を探して求める

正規表現を用いる

B - Delimiter

C - A+B+C

D - String Bags

E - Insert or Erase

F以降

参考にしたサイト等

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

`|`の位置を探して求める