AtCoder Beginner Contest 314をPythonで解く-Shinoryo's Weblog

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 314を, Pythonで解いてみた結果を書き連ねていこうと思います.

A - 3.14

問題文で与えられている円周率の文字列をスライスして出力すればよいです.

実装方針は, 例えば以下のようになります.

	# 入力
	N = int(input())
	A = []
	C = []
	for _ in range(N):
	C.append(int(input()))
	A_i = set(map(int, input().split()))
	A.append(A_i)
	X = int(input())

	# Xに賭けている人を対象に、賭けた目の個数の最小値C_minを調べる
	C_min = float('inf')
	for i in range(N):
	if X in A[i]:
	C_min = min(C_min, C[i])

	# Xに賭けていて、賭けた目の個数がC_minである人をansに格納する
	ans = [i + 1 for i in range(N) if X in A[i] and C[i] == C_min]

	# 出力
	print(len(ans))
	print(*ans)

色別に文字列をrotateさせればよいです. 「色 $C_{i}$ が塗られている文字の, 文字列 $S$ におけるインデックス」をあらかじめ調べておくと, 後の処理が楽になります.

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

	# C_counter[i]：色C[i]が塗られている文字の、文字列Sにおけるインデックス
	C_counter = [[] for _ in range(M)]
	for i in range(N):
	C_counter[C[i] - 1].append(i)

	# 出力文字列S_new
	S_new = ['' for _ in range(N)]
	for i in range(M):
	for j in range(len(C_counter[i])):
	# 色別にrotateする
	S_new[C_counter[i][(j + 1) % len(C_counter[i])]] = S[C_counter[i][j % len(C_counter[i])]]

	# 出力文字列を結合して表示
	print("".join(S_new))

クエリを愚直に実行するだけでは, TLEです.

ここでは, 全体に対する操作を別に考えることが必要です. 個々の文字が最後に変換された時刻と全体の大小が最後に変換された時刻を記録しておき, 個々の文字の変換の後に全体の大小の変換が記録されている場合, 大小変換を行うことにします.

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

	# 最後の変換情報を管理
	last_changed_time = [-1 for _ in range(N)] # 個々の文字が最後に変換された時刻
	last_whole_changed_time = -1 # 全体の大小が最後に変換された時刻
	last_whole_changed = 0 # -1：最後に全体が小文字、1：最後に全体が大文字

	# クエリを確認
	for query_i in range(Q):
	t, x, c = input().split()
	t = int(t)
	x = int(x)

	# 個々の文字は変換させてしまう
	if t == 1:
	S[x - 1] = c
	last_changed_time[x - 1] = query_i

	# 全体の大小の変換は情報だけ記録しておく
	elif t == 2:
	last_whole_changed = -1
	last_whole_changed_time = query_i
	else:
	last_whole_changed = 1
	last_whole_changed_time = query_i

	# 個々の文字の変換の後に全体の大小の変換が記録されている場合、変換する
	for i in range(N):
	if last_changed_time[i] < last_whole_changed_time:
	if last_whole_changed == -1:
	S[i] = S[i].lower()
	elif last_whole_changed == 1:
	S[i] = S[i].upper()

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

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