freee プログラミングコンテスト2023（AtCoder Beginner Contest 310）をPythonで解く-Shinoryo's Weblog

こんにちは, Shinoryoです.

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

A - Order Something Else

AtCoderドリンクの値段は, 次の2パターンです.

したがって, それらのうち安い方を出力すればよいです.

全ての $i$ , $j$ の組み合わせに対して, 一方が一方の上位互換になっているかを確かめればよいです. 下記の例のようにset()を使うと高速ですが, list()を使っても十分ACできると思います.

	import itertools

	# 入力
	N, M = map(int, input().split())
	P = []
	F = []
	for i in range(N):
	input_row = list(map(int, input().split()))
	P.append(input_row[0])
	F.append(set(input_row[2:]))

	# 条件チェック
	for i, j in itertools.permutations(range(N), 2):
	if P[i] < P[j]:
	continue
	if F[i] - F[j]:
	continue
	if P[i] <= P[j] and not F[j] - F[i]:
	continue
	print("Yes")
	exit()
	print("No")

棒を順番に見ていき, 今までに見たどの棒とも同じでない棒を見るたびにカウンタの値を $1$ 増やすことで, そのカウンタが答えになります.

「今までに見たどの棒とも同じでない棒」であるかを判断するには, 今までに見た棒を記録しておけば良いです. list()で格納してしまうと全体の計算量が $O (N^{2})$ となりTLEですが, set()で格納すれば全体の計算量が $O (N)$ となりACです.

	# 入力
	N = int(input())

	# 入力された文字列を記録していくset
	string_set = set()

	for _ in range(N):
	string_input = input()
	# 辞書順で若い方をsetに登録する
	string_set.add(min(string_input, string_input[::-1]))

	# 出力
	print(len(string_set))

順番に選手をチームに加えていく, またはその選手だけで新たなチームを作るということを順に行っていくことで, 全探索すればよいです. うまくset()を使うことで高速化できます.

	# teamsで表されるチームリストに、新たにnow_memberを追加する
	# max_member_num: メンバーの最大値
	# max_team_num: チーム数の条件
	# hate_list: あるメンバーと仲が悪いメンバーのset
	# ans: 条件を満たすチーム分けが存在すれば、ansに+1していく
	def add_member(now_member, teams, max_member_num, max_team_num, hate_list, ans):
	# メンバーの数が最大値を超えたら、チーム数が条件を満たすかを確認する
	if now_member > N:
	ans += len(teams) == max_team_num
	return ans

	# すでにあるチームにnow_memberを加える場合
	for team in teams:
	# そのチームにnow_memberと仲が悪いメンバーが存在しなければ加える
	if not hate_list[now_member] & team:
	team.add(now_member)
	ans = add_member(now_member + 1, teams, max_member_num, max_team_num, hate_list, ans)
	team.remove(now_member)

	# 新たにチームを作れる場合
	if len(teams) < max_team_num:
	teams.append(set([now_member]))
	ans = add_member(now_member + 1, teams, max_member_num, max_team_num, hate_list, ans)
	teams.pop()

	return ans

	# 入力
	N, T, M = map(int, input().split())

	# あるメンバーと仲が悪いメンバーのset
	hate_list = [set() for _ in range(N + 1)]

	for _ in range(M):
	A_i, B_i = map(int, input().split())
	hate_list[A_i].add(B_i)
	hate_list[B_i].add(A_i)

	# 出力
	print(add_member(1, [], N, T, hate_list, 0))

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