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

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

こんにちは, Shinoryoです.

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

1A - New Generation ABC
2B - How many?
3C - Distribution
4D - Sum of Maximum Weights
5E以降
6参考にしたサイト等

A - New Generation ABC

if文を用いて素直に分類すればよいです.

	# 入力
	N = int(input())

	# 出力
	if 1 <= N <= 125:
	print(4)
	elif 126 <= N <= 211:
	print(6)
	else:
	print(8)

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

B - How many?

$a + b + c \leq S$ を満たす $(a, b, c)$ に対して, $a \times b \times c \leq T$ を満たすかどうかを調べて数え上げます.

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

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

	# Sの条件を満たす(a, b, c)について、a * b * cの値を調査
	for a in range(S + 1):
	for b in range(S - a + 1):
	for c in range(S - a - b + 1):
	if a * b * c <= T:
	ans += 1

	# 出力
	print(ans)

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

C - Distribution

$i$ 番目のすぬけ君が $j$ 番目のすぬけ君に渡された宝石を手にする秒数を全て調査して, $i$ 番目のすぬけ君が最初に宝石を受け取る時刻をmin()などで取得することが考えられます. しかし, これだと時間計算量が $O (N^{2})$ となりTLEとなってしまいます.


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

	# 宝石をもらう秒数を計算
	Gettime = [[] for _ in range(N)]

	# i番目のすぬけ君がj番目のすぬけ君に渡された宝石を手にする秒数を調査
	for i in range(N):
	for j in range(N):
	temp = T[j]
	for k in range((i - j) % N):
	temp += S[(j + k) % N]
	Gettime[i].append(temp)

	# 出力
	for i in range(N):
	print(min(Gettime[i]))

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

ここで, $i$ 番目のすぬけ君は,

高橋君から $T_{i}$ 秒後にもらう
$(i - 1)$ 番目のすぬけ君がある時刻に受け取り, その $S_{i - 1}$ 秒後にもらう

のいずれかで最初に宝石を手にすることになります. これにより, 1.と2.の最小値で $T_{i}$ を更新していけばよいことが分かります. 実際には, 最初のすぬけ君に関しては1.と2.のどちらが本当に小さいかは真にはわからないので, ループは少なくとも2回繰り返す必要があります.

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

	# 宝石をもらう秒数を計算
	Gettime = [[] for _ in range(N)]

	# i番目のすぬけ君は、
	# 1) 高橋君からT_i秒後にもらう
	# 2) (i - 1)番目のすぬけ君がある時刻に受け取り、そのS_(i - 1)秒後にもらう
	# のいずれかで最初に宝石を手にする
	# 1)と2)の最小値でT_iを更新していけばよい
	# 最初のすぬけ君に関しては1)と2)のどちらが本当に小さいかは真にはわからないので、
	# ループは少なくとも2回繰り返す必要がある
	for _ in range(2):
	for i in range(N):
	T[i] = min(T[(i - 1)% N] + S[(i - 1)% N], T[i])

	# 出力
	for i in range(N):
	print(T[i])

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

と思いきや, $T_{i}$ が最も小さい $i$ 番目のすぬけ君からスタートすれば, ループは1回でよくなります. $T_{i}$ が最も小さい $i$ 番目のすぬけ君に与えられた宝石は, 全すぬけ君に与えられた最初の宝石であるからです.

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

	# 宝石をもらう秒数を計算
	Gettime = [[] for _ in range(N)]

	# i番目のすぬけ君は、
	# 1) 高橋君からT_i秒後にもらう
	# 2) (i - 1)番目のすぬけ君がある時刻に受け取り、そのS_(i - 1)秒後にもらう
	# のいずれかで最初に宝石を手にする
	# 1)と2)の最小値でT_iを更新していけばよい
	# 最初のすぬけ君に関しては1)と2)のどちらが本当に小さいかは真にはわからないので、
	# ループは少なくとも2回繰り返す必要がある

	# と思いきや、T_iが最も小さいi番目のすぬけ君からスタートすればよいのである
	# T_iが最も小さいi番目のすぬけ君に与えられた宝石は、
	# すぬけ君に与えられた最初の宝石であるからである

	temp = T.index(min(T))
	for i in range(temp, N + temp):
	T[i % N] = min(T[(i - 1)% N] + S[(i - 1)% N], T[i % N])

	# 出力
	for i in range(N):
	print(T[i])

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

D - Sum of Maximum Weights

$f (u, v) = w_{i}$ となる $(u, v)$ の総数を考えます. $(u, v)$ が $f (u, v) = w_{i}$ を満たすためには, 以下の2つの条件を満たさなくてはなりません.

頂点 $(u, v)$ を結ぶ道に辺 $i$ が含まれる.
その道に含まれる他の辺の重みが $w_{i}$ より小さい.

そこで, $w_{i}$ が小さい順に道をつなげていくことを考えます. 辺 $i$ の両端 $u_{i}$ , $v_{i}$ について

$size (u_{i})$ ： $u_{i}$ とすでに(重みが $w_{i}$ より小さい辺によって)道ができている他の点の数( $u_{i}$ を含める)
$size (v_{i})$ ： $v_{i}$ とすでに(重みが $w_{i}$ より小さい辺によって)道ができている他の点の数( $v_{i}$ を含める)

を調べ, $size (u_{i}) \times size (v_{i}) \times w_{i}$ を調べていくのです. 実際, この道をつなげる操作によって, $u_{i}$ が属するグループの点と $v_{i}$ が属するグループの点は, 初めてつながることになります. そして, その2点をつなぐ道に含まれる最も重い辺の重みは $w_{i}$ になります. 与えられるグラフが「木」であり, グラフ中に閉路が存在せず, 頂点 $(u, v)$ を結ぶ道は唯一であることから, この議論が成り立ちます.

例えば, 簡単に以下のようなグラフが与えられたと考えます.

図1 与えられるグラフの例. 丸はグラフの頂点(番号付き)を, 点線はこれからつなげていく辺(重み付き)を示す.

今の場合, まずつなげるのは頂点 $1$ と頂点 $2$ をつなげる辺です. この操作によって頂点 $1$ と頂点 $2$ は初めてつながり, その2点をつなぐ(唯一の)道に含まれる最も重い辺の重みは $1$ になります.

図2 図1のグラフにおいて頂点

1

と頂点

2

をつなげた結果.

次につなげるのは頂点 $2$ と頂点 $3$ をつなげる辺です. この操作によって頂点 $1$ と頂点 $3$ , 頂点 $2$ と頂点 $3$ は初めてつながり, それぞれをつなぐ(唯一の)道に含まれる最も重い辺の重みは $2$ になります.

図3 図1のグラフにおいて頂点

1

と頂点

2

, 頂点

2

と頂点

3

をつなげた結果.

この後の例は省略しますが, このようにして答えを求めていきます.

このようなデータ構造は, Union Findデータ構造と呼ばれます. 以下のコードでは, それから最低限を取り出して記述しています.

	# 入力
	N = int(input())

	# 辺情報リストの作成
	# uとvが辺でつながれているなら, u行目のリストにvと辺の重みw, [v, w]を加える
	# リストのインデックスは0から始まるため, N+1行の2次元配列
	# (0行目の存在は無視する)
	WUV_matrix = []
	for i in range(N - 1):
	u, v, w = [int(x) for x in input().split()]
	WUV_matrix.append([w, u - 1, v - 1])

	# f(u, v) = w_iとなる(u, v)の総数を考える
	# 条件1) 頂点(u, v)を結ぶ道に辺iが含まれる
	# 条件2) その道に含まれる他の辺の重みがw_iより小さい

	# w_iが小さい順に道をつなげていく
	# 辺iの両端u_i、v_iについて
	# u_iとすでに(重みがw_iより小さい辺によって)道ができている他の点の数(u_iを含める): size(u_i)
	# v_iとすでに(重みがw_iより小さい辺によって)道ができている他の点の数(v_iを含める): size(v_i)
	# を調べ、size(u_i) * size(v_i) * w_iを調べていく

	# 以上が成り立つのは、与えられるグラフが「木」であり、
	# グラフ中に閉路が存在せず、頂点(u, v)を結ぶ道は唯一であることから分かる

	WUV_matrix.sort()

	# このようなデータ構造は、Union Findデータ構造と呼ばれる

	# ある要素の親要素(根に近い方向)を格納する
	# 要素が根の場合は-(そのグループの要素数)を格納する
	parents = [-1] * N

	# 連結要素数を格納する
	size = N

	# find：xが属するグループの根を返す
	def find(x):
	# xが根ならそれ自身である
	if parents[x] < 0:
	return x
	# xが根でないなら、さらにその親要素に関して調べる(再帰)
	else:
	parents[x] = find(parents[x])
	return parents[x]

	# union：xとyをつなげる
	def union(x, y):
	# 根を探し、根同士をつなげる
	# 根同士をつなげることで、新たな親要素の上下関係
	x = find(x)
	y = find(y)
	# 根が一緒ならつながっているので特に何もしない
	if x == y:
	return

	# xが含まれる連結要素の方が小さく、yが含まれる連結要素の方が大きくなるようにする
	if parents[x] > parents[y]:
	x, y = y, x

	# xにyをくっつける操作
	# xとyをくっつけた連結要素の根は、xになる
	parents[x] += parents[y]
	parents[y] = x
	return

	# size：xが含まれる連結要素の要素数を返す
	def size(x):
	# xが含まれる連結要素の親を返せばよい
	return - 1 * parents[find(x)]

	# 実際に行ってみる

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

	# w_iが小さい辺iから調べる
	for w, u, v in WUV_matrix:
	# ansに格納する
	ans += w * size(u) * size(v)
	# uとvをつなげる
	union(u, v)

	# 出力
	print(ans)

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

あるいは, Union Findデータ構造を使用するということになったら, クラスとしてまとまっているものを使用してしまうのも手です. 以下は, nkmk様のWebページ(https://note.nkmk.me/python-union-find/)にあるUnion Findデータ構造のクラスへのリンクです.

クラスに関しては, 「AtCoder APG4bをPythonで解く(6)」EX24 - 時計の実装においても取り上げています.

E以降

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

参考にしたサイト等

「解説 - AtCoder Beginner Contest 214」
Editorial - AtCoder Beginner Contest 214
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
nkmk様による「PythonでのUnion-Find（素集合データ構造）の実装と使い方」
PythonでのUnion-Find（素集合データ構造）の実装と使い方 | note.nkmk.me
PythonでのUnion Findデータ構造（素集合データ構造）の実装とその使い方を説明する. まずはじめに最終形のクラスとその使い方のサンプルコードを示し, 後半で素朴な実装からいくつかの工夫を加えて最終形に至るまでを説明する. Union Find（素集合データ構造）の概要 PythonでのUnion Findの実装例サンプルコードのクラス...

AtCoder Beginner Contest 214をPythonで解く

A - New Generation ABC

B - How many?

C - Distribution

D - Sum of Maximum Weights

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