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

こんにちは, Shinoryoです.

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

A - Three-Point Shot

$X + 3 > Y$ の判定を行えばよいです.

	X, Y = sorted([int(x) for x in input().split()])

	if X + 3 > Y :
	print("Yes")
	else:
	print("No")

内積を愚直に計算すればよいです.

トーナメントを実際に再現します. 生き残った人のリストはもちろんのこと, 生き残った人がもともと何番目だったかの情報も必要なので, その番号のリストも作成し管理します.

求めるのは準優勝した人なので, トーナメントを再現するのは準決勝までとなります.

	# トーナメントの対戦をする関数
	# 生き残った人のリスト, 生き残った人がもともと何番目だったかのリストを出力
	def battle(rate_list, number_list):
	for i in range(len(rate_list)//2):
	if rate_list[i] > rate_list[i + 1]:
	del rate_list[i + 1]
	del number_list[i + 1]
	else:
	del rate_list[i]
	del number_list[i]
	return rate_list, number_list

	# 入力
	N = int(input())
	A = [int(x) for x in input().split()]

	# 生き残っている人がもともと何番目かを保存するリストを作成
	B = list(range(1, 2**N + 1))

	# トーナメントの実行(準決勝まで)
	for _ in range(N-1):
	A, B = battle(A, B)

	# 準優勝判定
	if A[0] > A[1]:
	print(B[1])
	else:
	print(B[0])

$1 \leq a_{i} \leq b_{i} \leq 10^{9}$ なので, 単純にいもす法を用いるのだとできません.

各々のサービス(サービス料金 $1$ 日あたり $c_{i}$ 円)を $a_{i}$ 日目から $b_{i}$ 日目まで利用するという入力データがあるわけですが, これを

に分解して考え, これをまとめて

と考え, データをまとめてソートします.

この料金増減イベントを再現していくことで求めます.

	# 入力
	N, C_snukeprime = [int(x) for x in input().split()]

	# 料金増減イベントの作成
	# a-1日目とa日目の間に増加、b日目とb+1日目の間に減少するイベント
	# つまり、a日目とa+1日目の間にc円増減するイベントをまとめる
	event = []
	for i in range(N):
	a, b, c = [int(x) for x in input().split()]
	a -= 1
	event.append([a,c])
	event.append([b,-c])

	# 料金増減イベントのソート
	event.sort()

	# 変数の準備
	# 答え(最小の料金合計)、各々の時刻の料金、今どの時刻を見ているのかの3変数
	ans = 0
	fee = 0
	t = 0

	# イベントはソート済みなので順番に見ていく
	for x,y in event:
	# 同じ時刻のイベントがある場合があるので、その可能性を考慮
	if x != t:
	ans += min(C_snukeprime,fee)*(x-t)
	t = x
	fee += y

	# 答えを出力
	print(ans)

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