デンソークリエイトプログラミングコンテスト2023（AtCoder Beginner Contest 309）をPythonで解く-Shinoryo's Weblog

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

こんにちは, Shinoryoです.

今回はデンソークリエイトプログラミングコンテスト2023（AtCoder Beginner Contest 309）を, Pythonで解いてみた結果を書き連ねていこうと思います.

1A - Nine
2B - Rotate
3C - Medicine
4D - Add One Edge
5E以降
6参考にしたサイト等

A - Nine

愚直に実行しても良いのですが, Yesとなる条件は「 $B - A = 1$ 」かつ「 $A$ が $3$ で割り切れない」になることを利用することができます.

	A, B = map(int, input().split())
	if B - A == 1 and A % 3 != 0:
	print("Yes")
	else:
	print("No")

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

B - Rotate

$A$ と同じ形の配列 $B$ を用意して, 外側なら1つずらす形で $A$ の値を $B$ にコピーすればよいです.

	import itertools

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

	# 答えを格納する配列
	B = [[None for _ in range(N)] for _ in range(N)]

	# 外側なら1つずらす形で、AをBにコピー
	for i, j in itertools.product(range(N), range(N)):
	if i == 0 or i == N - 1 or j == 0 or j == N - 1:
	if i == 0 and j < N - 1:
	B[i][j + 1] = A[i][j]
	elif i < N - 1 and j == N - 1:
	B[i + 1][j] = A[i][j]
	elif i == N - 1 and j > 0:
	B[i][j - 1] = A[i][j]
	elif i > 0 and j == 0:
	B[i - 1][j] = A[i][j]
	else:
	B[i][j] = A[i][j]

	# 出力
	for i in range(N):
	print("".join(B[i]))

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

C - Medicine

薬を飲む最終日から初日までさかのぼっていくと, 飲む薬の錠数は増えていきます. その数が $K$ を超えたところで, その日の翌日を出力します. もし最後まで $K$ を超えることがなければ, それは1日目から $K$ 錠以下だったのですから, 1日目を出力します.

	# 入力を受け取る
	N, K = map(int, input().split())

	# a_i日間、b_i錠の薬を受け取る
	a_b_list = []
	for _ in range(N):
	a, b = map(int, input().split())
	a_b_list.append((a, b))

	# a_iが大きい順にソート
	a_b_list.sort(reverse=True)

	# 累積和を計算してKを超えた日を求める
	cumulative_sum = 0
	for a, b in a_b_list:
	cumulative_sum += b

	# 累積和がKを超えた場合、その日の翌日を出力して終了
	if cumulative_sum > K:
	print(a + 1)
	exit()
	# Kを超えなかった場合、1日目を出力
	print(1)

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

D - Add One Edge

入力例1に似た状況を考えます.

頂点 $1$ と頂点 $N_{1} + N_{1}$ を結ぶ経路の長さ(辺の本数)の最小値が $d$ で, $d$ としてあり得る最大値を求める問題です. したがって, 直感的な言葉で言えば, 「頂点 $1$ から一番遠い頂点」と「頂点 $N_{1} + N_{2}$ から一番遠い頂点」を結んだ場合がそれにあたります.

ある頂点から一番遠い頂点は, 幅優先探索(breadth first search; BFS)を用いて求めることができます. ある根ノードで始まり隣接した全てのノードを探索し, そのそれぞれに対して同様のことを繰り返すことによって探索対象ノードを網羅する方法です.

	from collections import deque

	# starting_node番目のノードから他のノードへの最短距離のうち最長のものを返す
	# connection_data[i]: i番目のノードの隣のノードを表す集合
	def get_longest_distance(connection_data, starting_node):
	will_visit = deque([starting_node])

	distance = [-1 for _ in range(len(connection_data))]
	distance[starting_node] = 0

	while will_visit:
	now = will_visit.popleft()

	for next_node in connection_data[now]:
	if distance[next_node] < 0:
	will_visit.append(next_node)
	distance[next_node] = distance[now] + 1

	return max(distance)

	# 入力
	N_1, N_2, M = map(int, input().split())

	# connection[i]: i番目のノードの隣のノードを表す集合
	# 0番目は使用しない
	connection = [set() for _ in range(1 + N_1 + N_2)]

	# connectionを計算
	for _ in range(M):
	a_i, b_i = map(int, input().split())
	connection[a_i].add(b_i)
	connection[b_i].add(a_i)

	# 出力
	print(get_longest_distance(connection, 1) + get_longest_distance(connection, N_1 + N_2) + 1)

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

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

E以降

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

参考にしたサイト等

「解説 - デンソークリエイトプログラミングコンテスト2023（AtCoder Beginner Contest 309）」
Editorial - Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309)
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

デンソークリエイトプログラミングコンテスト2023（AtCoder Beginner Contest 309）をPythonで解く

A - Nine

B - Rotate

C - Medicine

D - Add One Edge

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