CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)をPythonで解く-Shinoryo's Weblog

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

こんにちは, Shinoryoです.

今回はCodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)を, Pythonで解いてみた結果を書き連ねていこうと思います.

1A - New Scheme
2B - Default Price
3C - Standings
- 3.1浮動小数点型の計算の精度を上げる
- 3.2整数の範囲で比較する
4D - Snuke Maze
5E以降
6参考にしたサイト等

A - New Scheme

問題文にある条件を愚直に判定すればよいです.

	S = list(map(int, input().split()))
	ok = True
	for i in range(len(S) - 1):
	if S[i + 1] - S[i] < 0:
	ok = False
	for i in range(len(S)):
	if S[i] < 100 or S[i] > 675:
	ok = False
	for i in range(len(S)):
	if S[i] % 25 != 0:
	ok = False
	if ok:
	print("Yes")
	else:
	print("No")

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

B - Default Price

皿の色 $C_{i}$ を順番に調べていって, 対応する金額の和を取っていけばよいです.

	# 入力
	N, M = map(int, input().split())
	C = list(input().split())
	D = list(input().split())
	P = list(map(int, input().split()))

	# デフォルトの値段を記録
	P_0 = P[0]

	# 皿と値段を辞書で対応させる
	price_dict = dict(zip(D, P[1:]))

	# 出力
	print(sum(price_dict[C_i] if C_i in price_dict else P_0 for C_i in C))

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

C - Standings

問題文のまま実装すると, 浮動小数点型の誤差によりWAとなります.

	# 入力
	N = int(input())

	# 成功率を計算
	success_rate = [None for _ in range(N)]
	for i in range(N):
	A_i, B_i = map(int, input().split())
	success_rate[i] = A_i / (A_i + B_i)

	# 参加者リストを生成
	participant_list = list(range(1, N + 1))

	# 参加者リストをソート
	participant_list.sort(key = lambda x: success_rate[x - 1], reverse = True)

	# 出力
	print(" ".join(list(map(str, participant_list))))

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

浮動小数点型の計算の精度を上げる

四倍精度浮動小数点形式を用いることで, この誤差を解消することができます.

	import numpy as np

	# 入力
	N = int(input())

	# 成功率を計算
	success_rate = np.empty(N, dtype=np.float128)
	for i in range(N):
	A_i, B_i = np.array(list(map(int, input().split())), dtype=np.float128)
	success_rate[i] = A_i / (A_i + B_i)

	# 参加者リストを生成
	participant_list = list(range(1, N + 1))

	# 参加者リストをソート
	participant_list.sort(key = lambda x: success_rate[x - 1], reverse = True)

	# 出力
	print(" ".join(list(map(str, participant_list))))

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

整数の範囲で比較する

$A_{i} / (A_{i} + B_{i}) < A_{j} / (A_{j} + B_{j})$ の大小比較は, $A_{i} (A_{j} + B_{j}) < A_{j} (A_{i} + B_{i})$ の大小比較にすることで, 整数の範囲で比較することができます. 高速な安定ソート(e.g. マージソート)のロジックにこれを組み込むことで, 問題を解くことができます.

	def merge_sort(arr):
	if len(arr) <= 1:
	return arr

	# リストを中央で分割
	middle = len(arr) // 2
	left_half = arr[:middle]
	right_half = arr[middle:]

	# 左半分と右半分を再帰的にソート
	left_half = merge_sort(left_half)
	right_half = merge_sort(right_half)

	# 2つのソート済みリストをマージ
	return merge(left_half, right_half)

	def merge(left, right):
	result = []
	left_idx, right_idx = 0, 0

	# 左右のサブリストを比較しながらマージ
	while left_idx < len(left) and right_idx < len(right):
	if (A[left[left_idx]] * (A[right[right_idx]] + B[right[right_idx]])) < (A[right[right_idx]] * (A[left[left_idx]] + B[left[left_idx]])):
	result.append(right[right_idx])
	right_idx += 1
	else:
	result.append(left[left_idx])
	left_idx += 1

	# 未処理の要素を結果に追加
	result.extend(left[left_idx:])
	result.extend(right[right_idx:])

	return result

	# 入力
	N = int(input())
	A = [None for _ in range(N)]
	B = [None for _ in range(N)]
	for i in range(N):
	A_i, B_i = map(int, input().split())
	A[i] = A_i
	B[i] = B_i

	# 参加者リストを生成
	participant_list = merge_sort(list(range(N)))

	# 参加者リストのインデックスを修正
	participant_list = [p + 1 for p in participant_list]

	# 出力
	print(" ".join(list(map(str, participant_list))))

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

D - Snuke Maze

原点マス $(0, 0)$ に対して, そのマスからどのマスに進めるかを調べて, 行くことができるマスを調べていくことを考えます. これを数え上げる有効な方法として, AtCoder Beginner Contest 177の「D - Friends」と同様に, 幅優先探索(breadth first search; BFS)と呼ばれる方法を用います.

	from collections import deque
	import itertools

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

	# snuke系定数
	snuke_len = 5
	snuke_list = ["s", "n", "u", "k", "e"]
	snuke_set = {"s", "n", "u", "k", "e"}

	# あるマスに対して、次のマスになりうるマスの一覧を作成
	linked_cells = [[set() for _ in range(W)] for _ in range(H)]
	for i, j in itertools.product(range(H), range(W)):
	if S[i][j] not in snuke_set:
	continue
	for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
	if 0 <= x < H and 0 <= y < W and S[x][y] == snuke_list[(snuke_list.index(S[i][j]) + 1) % snuke_len]:
	linked_cells[i][j].add((x, y))

	# deque型の変数を作成(まずは(0,0)からどのマスへ行けるかを調べるため, (0,0)を格納)
	queue = deque([(0, 0)])

	# (0, 0)からどのマスに行けるか調べている段階で、一度確認したマスのリスト
	# (0, 0)から(0, 0)へは訪れたことにする(Trueにする)
	visited = [[False for _ in range(W)] for _ in range(H)]
	visited[0][0] = True

	# 幅優先探索の実行
	# queueの各要素について、隣接するマスを調べる
	while queue:
	i, j = queue.popleft()
	for k, l in linked_cells[i][j]:
	# マス(H - 1, W - 1)に到達出来たら、Yesを出力し終了
	if (k, l) == (H - 1, W - 1):
	print("Yes")
	exit()
	# (i, j)から進めることが新たに判明したマス(k, l)に対し、
	# ・visited[k][l]をTrueにし,
	# ・queueに(k, l)を追加する
	# 新たに進めることが判明したわけではないマス(k, l)に対してはスキップ(continue)
	if visited[k][l]:
	continue
	visited[k][l] = True
	queue.append((k, l))

	# マス(H - 1, W - 1)に到達出来なかったので、Noを出力し終了
	print("No")

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

幅優先探索は, 他にも以下で取り上げています.

E以降

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

参考にしたサイト等

「解説 - CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)」
Editorial - AtCoder Beginner Contest 308
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
「ソート - Wikipedia」
ソート - Wikipedia
No description
takayg様の「Pythonでアルゴリズム（幅優先探索, bfs）」
Pythonでアルゴリズム（幅優先探索, bfs） - Qiita
#はじめに　pythonを使った幅優先探索の実装について解説していきます. （僕がいつも実装するやつを載せるだけです. ）　幅優先探索ではよく距離についての問題が出てくるので, 今回はある1頂点から各…
nkmk様の「Pythonのdequeでキュー, スタック, デック（両端キュー）を扱う」
Pythonのdequeでキュー, スタック, デック（両端キュー）を扱う | note.nkmk.me
Pythonの標準ライブラリcollectionsモジュールのdeque型を使うと, データをキューやスタック , デック（両端キュー）として効率的に扱うことができる. collections.deque --- コンテナデータ型 — Python 3.11.4 ドキュメント組み込みのリストlistをキューやスタック, デック（両端キュー）として使うことも可能だが, リス...

CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)をPythonで解く

A - New Scheme

B - Default Price

C - Standings

浮動小数点型の計算の精度を上げる

整数の範囲で比較する

D - Snuke Maze

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