トヨタ自動車プログラミングコンテスト2023＃4(AtCoder Beginner Contest 311)をPythonで解く-Shinoryo's Weblog

こんにちは, Shinoryoです.

A - First ABC

「Aが出現したか」「Bが出現したか」「Cが出現したか」のフラグ管理で解くことができます.

順番に全員が暇かを確かめていくことで解くことができます.

	# 入力
	N, D = map(int, input().split())
	S = [[s == "o" for s in input()] for _ in range(N)]

	# 使う変数の初期化
	max_vacation = 0
	current_vacation = 0

	# 1日ごとに調べる
	for i in range(D):
	if all(S[j][i] for j in range(N)):
	current_vacation += 1
	else:
	current_vacation = 0
	max_vacation = max(max_vacation, current_vacation)

	# 出力
	print(max_vacation)

頂点 $1$ から $A_{i}$ の指示にしたがって移動し続けていれば, いつかはサイクルに行き着くことになります.

サイクルに行き着いたかの判定は, 通った頂点を記録する列 $S$ に次の頂点が含まれるかで判定します. そして, $S$ の要素のうち, 次の頂点が入っているインデックスから先を出力すればよいです.

サイクルの要素を順番に出力するために, $S$ はlist()として記録しておく必要があります. しかし, $S$ に次の頂点が含まれるかの判定をlist()でやっているとTLEとなってしまいます.

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

	# 出発地点
	now = 1

	# ルートをlist()とset()で記録
	route = []

	# 実際にたどってみる
	while True:
	route.append(now)
	now = A[now - 1]

	# 訪れていれば、そこまでの間に有向閉路が存在するので、それを出力
	if now in route:
	route_result = route[route.index(now):]
	print(len(route_result))
	print(*route_result)
	exit()

この問題は, $S$ をset()としても記録しておき, $S$ に次の頂点が含まれるかの判定をset()で行うことで解決できます.

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

	# 出発地点
	now = 1

	# ルートをlist()とset()で記録
	route = []
	route_set = set()

	# 実際にたどってみる
	while True:
	route.append(now)
	route_set.add(now)
	now = A[now - 1]

	# 訪れていれば、そこまでの間に有向閉路が存在するので、それを出力
	if now in route_set:
	route_result = route[route.index(now):]
	print(len(route_result))
	print(*route_result)
	exit()

到達可能なマスを幅優先探索(breadth first search; BFS)で調べていくことで解くことができます. プレイヤーは岩のマスにぶつかるまでその方向に移動することになるので, 止まった場所を記録しておく配列と通過した場所を記録しておく配列は別にしておくことがポイントです.

	from collections import deque

	# 入力
	N, M = map(int, input().split())
	S = [list(i == "." for i in input()) for _ in range(N)]

	# 止まった場所を記録しておく配列
	stopped = [[False for _ in range(M)] for _ in range(N)]
	# 通過した場所を記録しておく配列
	visited = [[False for _ in range(M)] for _ in range(N)]
	# 初期位置
	stopped[1][1] = True
	visited[1][1] = True

	# 次に訪れる場所
	will_visit = deque([(1, 1)])

	# 幅優先探索
	while will_visit:
	now_x, now_y = will_visit.popleft()

	# 4方向へのループ
	for d_x, d_y in {(0,1),(1,0),(0,-1),(-1,0)}:
	now_xx, now_yy = now_x, now_y

	# 壁にあたるまで直進し続ける
	while S[now_xx + d_x][now_yy + d_y]:
	now_xx += d_x
	now_yy += d_y
	visited[now_xx][now_yy] = True

	# 止まった場所にまだ訪れていない場合
	if not stopped[now_xx][now_yy]:
	stopped[now_xx][now_yy] = True
	will_visit.append((now_xx, now_yy))

	# 出力
	print(sum(map(sum, visited)))

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

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