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

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

こんにちは, Shinoryoです.

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

目次[非表示]

1A - Cabbages
2B - Bouzu Mekuri
3C - Colorful Candies
4D - National Railway
5E以降
6参考にしたサイト等

A - Cabbages

$N \leq A$ の場合, 全てのキャベツが $1$ 個 $X$ 円で購入できるので, 合計金額は $N X$ 円です.

$N > A$ の場合, $A$ 個のキャベツが $1$ 個 $X$ 円で購入出来て, $N - A$ 個のキャベツが1個 $Y$ 円で購入できるので, 合計金額は $A X + (N - A) Y$ 円です.

以上から, どちらの場合も合計金額を $\min (N, A) \times X + \max (0, N - A) \times Y$ 円と書けます.

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

	# 出力
	print(min(N, A) * X + max(0, N - A) * Y)

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

B - Bouzu Mekuri

文字列 $S$ の先頭から見て初めて $1$ が現れる場所を $X$ 文字目とします(ただし, 先頭から $0$ 文字目, $1$ 文字目と数えることとし, これはインデックスにそのまま一致します). $X$ が偶数ならばそのカードを高橋君が食べ, $X$ が奇数ならばそのカードを青木君が食べることになります.

文字列 $S$ にある文字が含まれるかどうかを探索するには, .find()を使用することができます. .find()を使う場合, 先頭から探索します.

	# 入力
	N = int(input())
	S = input()

	# 最初に1が出てくる位置を検索
	firstone = S.find("1")

	# firstoneが偶数ならTakahashi、奇数ならAoki
	if firstone % 2 == 0:
	print("Takahashi")
	else:
	print("Aoki")

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

.find()を使わなくても, 明示的に探索の操作を行えばよいです.

	# 入力
	N = int(input())
	S = input()

	# 最初に1が出てくる位置を検索
	for i in range(N):
	if S[i] == "1":
	firstone = i
	break

	# firstoneが偶数ならTakahashi、奇数ならAoki
	if firstone % 2 == 0:
	print("Takahashi")
	else:
	print("Aoki")

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

C - Colorful Candies

1つの区間に含まれるキャンディの色の種類数を求めるには「区間内の $K$ 個のキャンディを一つずつ見て, 区間内の色の種類数を数える」という方法が考えられます. しかし, これだと時間計算量に $O (K (N - K + 1))$ になり, TLEです.

	from collections import deque

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

	# cから切り出したdeque
	cslice = deque(c[0:K])

	# 答えを格納する変数
	ans = len(set(cslice))

	# キャンディをもらう全通り
	for i in range(N - K):
	# 左端とこれから加えようとするものが同じなら
	if c[i + K] == cslice[0]:
	# 更新の操作だけする
	cslice.popleft()
	cslice.append(c[i + K])
	# そうでなければ
	else:
	# 更新の操作に加えて種類の最高記録を更新
	cslice.popleft()
	cslice.append(c[i + K])
	ans = max(ans, len(set(cslice)))

	# 出力
	print(ans)

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

そこで, 「各 $i = 1, 2, \dots, N - K$ に対する $[i, i + K - 1]$ と $[i + 1, i + K]$ のキャンディの純粋に差分を確認する」という方法を考えます. 辞書型を用いて ${1 : number (1), 2 : number (2), 3 : number (3), \dots}$ のように各キャンディの個数を記録し, それを変化させていく方法を考えます. また, キャンディの種類数を別に記録しておけば, 辞書型のvalueを合計する時間計算量を減らすことができます.

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

	# 連想配列を作る
	# Pythonには辞書型という嬉しいものがある
	c_dict = {x : 0 for x in set(c)}

	# 最初の一歩
	# index 0からk-1までのcを見て、その情報をc_dictに記録
	for i in range(K):
	c_dict[c[i]] += 1
	# index 0からk-1までを見たときの種類数を調査
	temp = sum(c_dict[i] != 0 for i in c_dict)
	# 答えを格納する変数
	ans = temp

	# これ以降は調査する場所を1つずつずらしていく
	for i in range(1, N-K+1):
	# 先頭のものを削除
	c_dict[c[i-1]] -= 1
	# 削除した結果0になったら、種類数が1減る
	if c_dict[c[i-1]] == 0:
	temp -= 1
	# 後ろに新しいものを追加
	c_dict[c[i+K-1]] += 1
	# 追加した結果1になったら、種類数が1増える
	if c_dict[c[i+K-1]] == 1:
	temp += 1
	# ansを更新
	ans = max(ans, temp)

	# 出力
	print(ans)

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

D - National Railway

この問題は駅 $(i_{s}, j_{s})$ から駅 $(i_{f}, j_{f})$ までの鉄道を敷設するのにかかる最小の値段を動的計画法(dynamic programming)を用いて考えていきます.

その際, $i_{s} <= i_{f}$ は一般に仮定してよいことに注意してください. 駅 $(i_{s}, j_{s})$ から駅 $(i_{f}, j_{f})$ までの鉄道を敷設するのにかかる最小の値段は, 駅 $(i_{f}, j_{f})$ から駅 $(i_{s}, j_{s})$ までの鉄道を敷設するのにかかる最小の値段と同一であることから, そのように仮定してよいことが分かります.

また, $j_{s} <= j_{f}$ も仮定します. $j_{s} >= j_{f}$ のパターンは, 例えば行列 $A_{i, j}$ の左右を反転させることによって実現できます. (これに関しては, $A_{i, j}$ の左右を反転させたものに対して同様の作業を繰り返さなければならないことに注意してください. )

中間地点 $(i, j)$ を境に2段階に分けて考えると楽になります.

青木君が一方の駅をすでに建設して現在 $(i, j)$ にいるとき, それまでにかかった費用として考えられる最小値(dp[i][j])
1. $(i, j)$ に駅を立てた
2. $(i - 1, j)$ から $(i, j)$ に線路を引いて移動してきた
3. $(i, j - 1)$ から $(i, j)$ に線路を引いて移動してきた
2つ目の駅を $(i, j)$ に建てて青木君がどこかへ飛び立ったとき, そこまでにかかった費用として考えられる最小値(X[i][j])
1. $(i - 1, j)$ から $(i, j)$ に線路を引いて移動してきて, $(i, j)$ に駅を立てた
2. $(i, j - 1)$ から $(i, j)$ に線路を引いて移動してきて, $(i, j)$ に駅を立てた

$A_{i, j}$ の左右反転には, 例えば.reverse()を用いると便利です.

多次元配列の最小値を求めるには, 例えば多次元リストの平坦化を用いると便利です. Pythonには, itertoolsモジュールのitertools.chain.from_iterable()があり, itertools.chain.from_iterable(matrix)のような形で, 2次元配列を1次元配列にすることができます.

なお, Python (3.8.2)で実行するとTLEになります. PyPy3 (7.3.0)で実行することでACです.

	import itertools

	# 入力
	H, W, C = [int(x) for x in input().split()]
	A_matrix = [[int(x) for x in input().split()] for _ in range(H)]

	INF = float('inf')

	# (is, js) → (if, jf)
	# is <= if は一般に仮定してよい
	# まずは、js <= jf とする

	# dp[i][j]: 青木君が一方の駅をすでに建設して、現在(i,j)にいるとき
	# それまでにかかった費用として考えられる最小値
	# 考えられるパターン
	# 1) (i, j)に駅を立てた
	# 2) (i-1, j)から(i,j)に線路を引いて移動してきた
	# 3) (i, j-1)から(i,j)に線路を引いて移動してきた

	dp = [[INF for _ in range(W)] for _ in range(H)]

	for i in range(H):
	for j in range(W):
	if i == 0 and j == 0:
	dp[i][j] = A_matrix[i][j]
	elif i == 0:
	dp[i][j] = min(A_matrix[i][j], dp[i][j-1] + C)
	elif j == 0:
	dp[i][j] = min(A_matrix[i][j], dp[i-1][j] + C)
	else:
	dp[i][j] = min(A_matrix[i][j], dp[i][j-1] + C, dp[i-1][j] + C)

	# X[i][j]: 2つ目の駅を(i, j)に建てて青木君がどこかへ飛び立ったとき
	# そこまでにかかった費用として考えられる最小値
	# 考えられるパターン
	# 2) (i-1, j)から(i,j)に線路を引いて移動してきて、(i,j)に駅を立てた
	# 3) (i, j-1)から(i,j)に線路を引いて移動してきて、(i,j)に駅を立てた

	X = [[INF for _ in range(W)] for _ in range(H)]

	for i in range(H):
	for j in range(W):
	if i == 0 and j == 0:
	continue
	elif i == 0:
	X[i][j] = dp[i][j-1] + C + A_matrix[i][j]
	elif j == 0:
	X[i][j] = dp[i-1][j] + C + A_matrix[i][j]
	else:
	X[i][j] = min(dp[i][j-1] + C + A_matrix[i][j], dp[i-1][j] + C + A_matrix[i][j])

	# Xの最小値を格納
	ans1 = min(itertools.chain.from_iterable(X))

	# 次には、js >= jf とする
	# そのためには、A_matrixを左右反転させればよい
	for i in range(H):
	A_matrix[i].reverse()

	# dp[i][j]: 青木君が一方の駅をすでに建設して、現在(i,j)にいるとき
	# それまでにかかった費用として考えられる最小値
	# 考えられるパターン
	# 1) (i, j)に駅を立てた
	# 2) (i-1, j)から(i,j)に線路を引いて移動してきた
	# 3) (i, j-1)から(i,j)に線路を引いて移動してきた

	dp = [[INF for _ in range(W)] for _ in range(H)]

	for i in range(H):
	for j in range(W):
	if i == 0 and j == 0:
	dp[i][j] = A_matrix[i][j]
	elif i == 0:
	dp[i][j] = min(A_matrix[i][j], dp[i][j-1] + C)
	elif j == 0:
	dp[i][j] = min(A_matrix[i][j], dp[i-1][j] + C)
	else:
	dp[i][j] = min(A_matrix[i][j], dp[i][j-1] + C, dp[i-1][j] + C)

	# X[i][j]: 2つ目の駅を(i, j)に建てて青木君がどこかへ飛び立ったとき
	# そこまでにかかった費用として考えられる最小値
	# 考えられるパターン
	# 2) (i-1, j)から(i,j)に線路を引いて移動してきて、(i,j)に駅を立てた
	# 3) (i, j-1)から(i,j)に線路を引いて移動してきて、(i,j)に駅を立てた

	X = [[INF for _ in range(W)] for _ in range(H)]

	for i in range(H):
	for j in range(W):
	if i == 0 and j == 0:
	continue
	elif i == 0:
	X[i][j] = dp[i][j-1] + C + A_matrix[i][j]
	elif j == 0:
	X[i][j] = dp[i-1][j] + C + A_matrix[i][j]
	else:
	X[i][j] = min(dp[i][j-1] + C + A_matrix[i][j], dp[i-1][j] + C + A_matrix[i][j])

	# Xの最小値を格納
	ans2 = min(itertools.chain.from_iterable(X))

	# 出力
	print(min(ans1, ans2))

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

E以降

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

参考にしたサイト等

「解説 - AtCoder Beginner Contest 210」
Editorial - AtCoder Beginner Contest 210
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
nkmk様による「Pythonで文字列を検索（〜を含むか判定, 位置取得, カウント）」
Pythonで文字列を検索（〜を含むか判定, 位置取得, カウント） | note.nkmk.me
Pythonで文字列を検索して任意の文字列を含むか判定したり, その位置を取得したり, ヒットした個数をカウントしたりする方法について説明する. 任意の文字列を含むか判定: in演算子任意の文字列の位置を取得: find(), rfind() 任意の文字列の個数をカウント: count() 単語を検索, 個数をカウント大文字小文字を区別せずに...
nkmk様による「Pythonでリストや文字列を逆順に並べ替え（reverse, reversed）」
Pythonでリストや文字列を逆順に並べ替え（reverse, reversed） | note.nkmk.me
Pythonでリストの要素を逆順に並べ替えるにはreverse(), reversed()およびスライスを使った方法がある. 文字列やタプルを逆順に並べ替えたい場合はreversed()かスライスを使う. ここでは以下の内容について説明する. リスト型のメソッド reverse(): 元のリストを逆順に並べ替え組み込み関数 reversed(): 要素を逆順に取り...
nkmk様による「Pythonでflatten（多次元リストを一次元に平坦化）」
Pythonでflatten（多次元リストを一次元に平坦化） | note.nkmk.me
Pythonで多次元のリスト（リストのリスト, ネストしたリスト）を一次元に平坦化する方法について説明する. 2次元のリストを平坦化itertools.chain.from_iterable()sum()リスト内包表記処理速度の差 itertools.chain.from_iterable() sum() リスト内包表記処理速度の差 3次元以上のリストや不規則なリストを平坦化 NumPy配...

AtCoder Beginner Contest 210をPythonで解く

A - Cabbages

B - Bouzu Mekuri

C - Colorful Candies

D - National Railway

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