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

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

こんにちは, Shinoryoです.

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

1A - Rock-paper-scissors
2B - Nuts
3C - Tour
4D - Cooking
5E以降
6参考にしたサイト等

A - Rock-paper-scissors

$x$ と $y$ が等しければ同じ数を, $x$ と $y$ が異なればそれらではない数を出力すればよいです. もちろん, 全ての場合を列挙しても構いません.

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

	# 出力
	# 一緒だった場合はその値を出力
	if x == y:
	print(x)
	# そうでなければxでもyでもない数を出力
	else:
	print(({0, 1, 2} - {x} - {y}).pop())

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

B - Nuts

リスト $A$ の各要素から $10$ を引いて下限を $0$ にしたリストを合計すればよいことが分かります.

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

	# 出力
	# 10を引いて下限を0にしたリストを合計すればよい
	print(sum([max(0, A_i - 10) for A_i in A]))

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

C - Tour

ある都市に対して, その都市からどの都市に道がつながっているかを調べて, 行くことができる都市を数え上げることを考えます. これを数え上げる有効な方法として, AtCoder Beginner Contest 177の「D - Friends」と同様に, 幅優先探索(breadth first search; BFS)と呼ばれる方法を用います.

	from collections import deque

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

	# 都市のつながりのリストの作成
	# AからBに道がつながっているなら, A行目のリストにBを加える
	# リストのインデックスは0から始まるため, N+1行の2次元配列
	# (0行目の存在は無視する)
	g = [[] for _ in range(N+1)]
	for i in range(M):
	A, B = [int(x) for x in input().split()]
	g[A].append(B)

	# 答えを格納する変数
	ans = 0

	# 各都市に対してループ
	for i in range(1,N+1):
	# deque型の変数を作成(まずはiからどの都市へ行けるかを調べるため, iを格納)
	queue = deque([i])

	# iからどの都市に行けるか調べている段階で、一度確認した都市のリスト
	# iからiへは訪れたことにする(Trueにする)
	visited = [False]*(N+1)
	visited[i] = True

	# iから行ける都市の数を格納する変数
	# iからiへは行けるから、初期値は1
	citygroup_number = 1

	# 幅優先探索の実行
	# queueの各要素について友達を調べる
	while queue:
	k = queue.popleft()
	for j in g[k]:
	# iから行けることが新たに判明した都市jに対し、
	# ・citygroup_numberに1を足し,
	# ・visited[j]をTrueにし,
	# ・queueにjを追加する
	# 新たに判明したわけではない都市jに対してはスキップ(continue)
	if visited[j]:
	continue
	citygroup_number += 1
	visited[j] = True
	queue.append(j)

	ans += citygroup_number

	# 出力
	print(ans)

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

D - Cooking

$T_{1}$ から $T_{N}$ までの和を $T_{sum} = \sum_{i = 1}^{N} T_{i}$ とします. 1つ目のオーブンを使う時間が2つ目のオーブンを使う時間以上であると仮定してよく, このとき, 1つ目のオーブンを使う時間は $T_{sum} / 2$ 以上になります. つまり, $T_{1}$ から $T_{N}$ までの部分和で作れる数のうち, $T_{sum} / 2$ 以上の最小値を求めればよいことが分かります.

この問題は「 $T_{1}$ から $T_{N}$ までの部分和で $x$ を作ることができるか？」という問題を各 $x$ に関する解けば十分です. $x$ は $0$ から $T_{sum}$ まで調べます. 以下ではdp[i][j]を $T_{1}$ から $T_{i}$ までの部分和で数 $j$ を作ることができるか(True or False)とします.

$T$ を用いずに数 $0$ を作ることができるので, dp[0][0] = Trueとします. $T$ を用いずに数 $1, 2, \dots$ を作ることはできないので, dp[0][1], dp[0][2], ……はFalseのままにしておきます.

原則として, $T_{1}$ から $T_{i}$ までの部分和で数 $j$ を作ることができるならば, $T_{1}$ から $T_{i + 1}$ までの部分和で数 $j$ を作ることができます(dp[i + 1][j] = dp[i][j]).

$T_{i + 1} \leq j$ ならば, $T_{1}$ から $T_{i}$ までの部分和で数 $(j - T_{i + 1})$ を作ることができることを条件に, $T_{1}$ から $T_{i + 1}$ までの部分和で数 $j$ を作ることができます(dp[i + 1][j] = dp[i][j - T[i]]).

以上のようにすることで, 「 $T_{1}$ から $T_{N}$ までの部分和で $x$ を作ることができるか？」という問いに答えることができます. Python (3.8.2)ではTLEですが, PyPy3 (7.3.0)ではACとなります.

	import math

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

	# Tの和を格納
	Tsum = sum(T)

	# 部分和問題を動的計画法(dp)で解く
	# dp[i][j]：T_1からT_iまでの部分和で数jを作ることができるか？
	# (True：作れる、False：作れない)

	# (N + 1)*(Tsum + 1)の配列を作成
	dp = [[False for _ in range(Tsum + 1)] for _ in range(N + 1)]

	# 初期値としてdp[0][0] = Trueを格納
	# (Tを用いずに数0を作ることができる)
	dp[0][0] = True
	# Tを用いずに数1、2、……を作ることはできないので、
	# dp[0][1]、dp[0][2]、……はFalseのままにしておく

	# Tの個数Nでループ
	for i in range(N):
	# Tsumでループ
	for j in range(Tsum + 1):
	# dp[i + 1][j]がTrueかFalseかを調べたい

	# 原則として、T_1からT_iまでの部分和で数jを作ることができるならば、
	# T_1からT_(i + 1)までの部分和で数jを作ることができる
	# (dp[i + 1][j] = dp[i][j])

	# T_(i + 1) <= jならば、T_1からT_iまでの部分和で
	# 数(j - T_(i + 1))を作ることができることを条件に、
	# T_1からT_(i + 1)までの部分和で数jを作ることができる
	# (dp[i + 1][j] = dp[i][j - T[i]])

	if T[i] <= j:
	dp[i + 1][j] = dp[i][j - T[i]] or dp[i][j]
	else:
	dp[i + 1][j] = dp[i][j]

	# 以上で、T_1からT_iまでの部分和で数jを作ることができるかという問いに対して答えられる
	# T_1からT_Nまでの部分和で作れる数のうち、Tsum / 2以上の最小値を求めればよい
	# Tsum / 2以上の最小の整数を格納
	threshold = math.ceil(Tsum / 2)

	# thresholdからTsumまでループ
	for k in range(threshold, Tsum + 1):
	# T_1からT_Nまでの部分和で数kを作れるならば、kを出力して終了
	if dp[N][k]:
	print(k)
	break

	# T_1からT_Nまでの部分和でTsumは必ず作れるから、ここに来ることはない

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

E以降

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

参考にしたサイト等

「解説 - AtCoder Beginner Contest 204」
Editorial - AtCoder Beginner Contest 204
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder Beginner Contest 204をPythonで解く

A - Rock-paper-scissors

B - Nuts

C - Tour

D - Cooking

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