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

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

こんにちは, Shinoryoです.

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

1A - I Scream
2B - Job Assignment
- 2.1計算にちょっと時間がかかる方法
- 2.2計算にそこまで時間がかからない方法
3C - Squared Error
4D - Journey
5E以降
6参考にしたサイト等
7脚注

A - I Scream

条件を書いてif文で分岐させれば問題ないです.

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

	# 出力
	if A + B >= 15 and B >= 8:
	print(1)
	elif A + B >= 10 and B >= 3:
	print(2)
	elif A + B >= 3:
	print(3)
	else:
	print(4)

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

B - Job Assignment

考え方はいくつかあります.

計算にちょっと時間がかかる方法

まずは,

1人でどちらの仕事もやるパターン
2人でどちらの仕事もやるパターン

の全場合を探索し, 最小値を出す方法です. 1人でどちらの仕事もやるパターンを全て調べるのに $O (N)$ , 2人でどちらの仕事もやるパターンを全て調べるのに $O (N^{2})$ かかるので, この方法だと最終的に $O (N^{2})$ だけかかります.

	import itertools

	# 入力
	N = int(input())
	A = []
	B = []
	for _ in range(N):
	A_i, B_i = [int(x) for x in input().split()]
	A.append(A_i)
	B.append(B_i)

	# 答えを格納する変数
	# 10^6はかからないと踏んで
	ans = 10**6

	# 1人で行う場合を探索
	for i in range(N):
	ans = min(ans, A[i] + B[i])

	# 2人で行う場合を探索
	for i,j in itertools.permutations(range(N),2):
	ans = min(ans, max(A[i], B[j]))

	# 出力
	print(ans)

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

計算にそこまで時間がかからない方法

2人でどちらの仕事もやるパターンを全探索しないでやることもできますね.

1人でどちらの仕事もやるパターン
$A$ の仕事に最も時間がかからない人との組み合わせのパターン
$B$ の仕事に最も時間がかからない人との組み合わせのパターン

の全場合を探索し, 最小値を出す方法です. 上記すべてのパターンを全て調べるのに $O (N)$ かかるので, この方法だと最終的に $O (N)$ だけかかります.

	# 入力
	N = int(input())
	A = []
	B = []
	for _ in range(N):
	A_i, B_i = [int(x) for x in input().split()]
	A.append(A_i)
	B.append(B_i)

	# 答えを格納する変数
	# 10^6はかからないと踏んで
	ans = 10**6

	# 1人で行う場合を探索
	for i in range(N):
	ans = min(ans, A[i] + B[i])

	# 2人で行う場合を探索

	# Aのかかる時間が最も短い人を採用した場合
	# Aのかかる最も短い時間を格納
	A_min = 10**6
	# Aのかかる時間が最も短い人リストを格納
	A_min_number = []
	# A_min、A_min_numberを調査
	for i in range(N):
	if A_min > A[i]:
	A_min = A[i]
	A_min_number = [i]
	elif A_min == A[i]:
	A_min_number.append(i)

	# A_min_numberの要素数(時間最低タイが存在しないか)で場合分け
	if len(A_min_number) > 1:
	# 時間最低タイが存在すれば、とりあえずmin(B)でOK
	ans = min(ans, max(A_min, min(B)))
	else:
	# 時間最低タイが存在しなければ、インデックスA_min_number[0]を除いたB_tempを用意しmin(B_temp)
	ans = min(ans, max(A_min, min(B[:A_min_number[0]] + B[A_min_number[0] + 1:])))

	# Bのかかる時間が最も短い人を採用した場合
	# Bのかかる最も短い時間を格納
	B_min = 10**6
	# Bのかかる時間が最も短い人リストを格納
	B_min_number = []
	# B_min、B_min_numberを調査
	for i in range(N):
	if B_min > B[i]:
	B_min = B[i]
	B_min_number = [i]
	elif B_min == B[i]:
	B_min_number.append(i)

	# B_min_numberの要素数(時間最低タイが存在しないか)で場合分け
	if len(B_min_number) > 1:
	# 時間最低タイが存在すれば、とりあえずmin(A)でOK
	ans = min(ans, max(B_min, min(A)))
	else:
	# 時間最低タイが存在しなければ、インデックスB_min_number[0]を除いたA_tempを用意しmin(A_temp)
	ans = min(ans, max(B_min, min(A[:B_min_number[0]] + A[B_min_number[0] + 1:])))

	# 出力
	print(ans)

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

上で書いたようなものをよりスマートに書き直したようなものが, AtCoderの解説に載っていました.

C - Squared Error

問題文にあることを律儀に実行すると, $O (N^{2})$ だけかかり, TLEです.

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

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

	# 律儀に加えていく
	for i in range(1,N):
	for j in range(i):
	ans += (A[i] - A[j])**2

	# 出力
	print(ans)

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

そこで, 例えば次のように考えます.

\begin{aligned} \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} {(A_{i} - A_{j})}^{2} & = \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_{i}^{2} - 2 A_{i} A_{j} + A_{j}^{2}) \\ (1) & = \sum_{i = 2}^{N} (i - 1) A_{i}^{2} - 2 \sum_{i = 2}^{N} (A_{i} \sum_{j = 1}^{i - 1} A_{j}) + \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} A_{j}^{2} \end{aligned}

それぞれ累積和や二乗の累積和は $O (N)$ で事前に求めておくことができます. よって, このように展開するだけで $O (N)$ で解くことができます.

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

	# Aの累積和を格納
	Aruiseki = []
	temp = 0
	for i in range(N):
	temp += A[i]
	Aruiseki.append(temp)

	# Aの2乗の累積和を格納
	Asquaredruiseki = []
	temp = 0
	for i in range(N):
	temp += A[i]**2
	Asquaredruiseki.append(temp)

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

	# 計算
	for i in range(1,N):
	ans += i * (A[i]**2)
	ans -= 2 * A[i] * Aruiseki[i-1]
	ans += Asquaredruiseki[i-1]

	# 出力
	print(ans)

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

あるいは, 次のようにも考えることができます. $\sum$ の上下限は, 差の二乗をとる際に同じ組み合わせが現れないようにしてあります. $A_{i} - A_{i} = 0$ ですので, $i$ も $j$ も両方 $1$ から $N$ まで足し上げて $1 / 2$ してもいいんですね.

\begin{aligned} \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} {(A_{i} - A_{j})}^{2} & = \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} {(A_{i} - A_{j})}^{2} \\ = \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} (A_{i}^{2} - 2 A_{i} A_{j} + A_{j}^{2}) \\ = \frac{1}{2} (N \sum_{i = 1}^{N} A_{i}^{2} - 2 \sum_{i = 1}^{N} (A_{i} \sum_{j = 1}^{N} A_{j}) + N \sum_{j = 1}^{N} A_{j}^{2}) \\ (2) & = N \sum_{i = 1}^{N} A_{i}^{2} - {(\sum_{j = 1}^{N} A_{j})}^{2} \end{aligned}

ここまで変形してしまえば, ここまでスマートにコーディングすることができます.

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

	# 出力
	print(N * sum([x2 for x in A]) - sum(A)2)

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

D - Journey

最終的にグラフが連結になるためには, 最初にいる頂点 $1$ 以外の $N - 1$ 個の頂点を新たに訪れなければなりません. つまり, 「今までに訪れていない頂点に新たに訪れる」ということを $N - 1$ 回行わなければなりません.

$S$ ：今までに訪れたことのある頂点の集合
$| S |$ ： $S$ の要素数

とすると, 新しい頂点に訪れる確率は $(N - | S |) / N$ となります.

ここで, 確率 $p$ ( $p \neq 0$ )で成功する試行を, 成功するまで行うときの試行回数(最後の成功した回も含む)の期待値は $1 / p$ であることが知られています^*1.

この事実を用いれば, $| S | = 1$ のときから $| S | = N - 1$ のときまで $N / (N - | S |)$ を足し上げて,

\begin{array}{r} (3) & \frac{N}{N - 1} + \frac{N}{N - 2} + \dots + \frac{N}{1} \end{array}

が, 求める答えになります. これは $O (N)$ で求めることが可能です.

	# 入力
	N = int(input())

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

	# 今まで訪れたことのない頂点を訪れるまでにかかる回数の期待値を加えていく
	for i in range(1,N):
	ans += N / (N - i)

	# 出力
	print(ans)

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

E以降

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

参考にしたサイト等

「解説 - AtCoder Beginner Contest 194」
Editorial - AtCoder Beginner Contest 194
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
難波博之様による「幾何分布の具体例と期待値，無記憶性について」(学びTimes：高校数学の美しい物語)
幾何分布の具体例と期待値，無記憶性について | 高校数学の美しい物語
幾何分布の期待値（平均），分散，無記憶性について３つの具体例を交えて解説します.

脚注

*1 :これは以下のようにして証明される.

Bernoulli試行(Bernoulli trial)(取り得る結果が「成功」「失敗」の2つのみであり, 各試行において成功の確率が同じであるランダム試行)を繰り返して初めて成功させるまでの試行回数 $X$ の分布は, 幾何分布(geometric distribution)として知られている. 以下, そのBernoulli試行において, 「成功」する確率を $p$ ( $p > 0$ )とする. $X = k$ のとき, $k - 1$ 回「失敗」した後に $1$ 回「成功」することになるので,

\begin{aligned} (4) & P (X = k) & = p {(1 - p)}^{k - 1} \end{aligned}

となる.

図「成功」の確率が

p = 1 / 2

p = 1 / 3

p = 1 / 4

p = 1 / 5

の幾何分布.

この幾何分布の期待値を計算すると,

\begin{aligned} E (X) & = \sum_{k = 1}^{\infty} k P (X = k) \\ = \sum_{k = 1}^{\infty} k p {(1 - p)}^{k - 1} \\ = p \sum_{k = 1}^{\infty} k {(1 - p)}^{k - 1} \\ = - p \sum_{k = 1}^{\infty} \frac{d}{d p} {(1 - p)}^{k} \\ = - p \frac{d}{d p} \sum_{k = 1}^{\infty} {(1 - p)}^{k} \\ = - p \frac{d}{d p} \frac{1 - p}{1 - (1 - p)} \\ (5) & = \frac{1}{p} \end{aligned}

となる.

AtCoder Beginner Contest 194をPythonで解く

A - I Scream

B - Job Assignment

計算にちょっと時間がかかる方法

計算にそこまで時間がかからない方法

C - Squared Error

D - Journey

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