サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）をPythonで解く-Shinoryo's Weblog

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

こんにちは, Shinoryoです.

今回はサイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）を, Pythonで解いてみた結果を書き連ねていこうと思います.

1A - AtCoder Quiz 2
2B - Maritozzo
3C - Neo-lexicographic Ordering
4D - Strange Lunchbox
5E以降
6参考にしたサイト等

A - AtCoder Quiz 2

素直に条件式を記述すればよいです.

	# 入力
	X = int(input())

	# 出力
	if X < 40:
	print(40 - X)
	elif X < 70:
	print(70 - X)
	elif X < 90:
	print(90 - X)
	else:
	print("expert")

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

B - Maritozzo

文字列 $S_{1}$ , $S_{2}$ , $S_{3}$ をリスト $S$ に格納します. そして, 文字列 $T$ を1文字目から順に調べていき, 対応する文字列をリスト $S$ から探してきて, 答えとなる文字列にくっつけていきます. 文字列をくっつける操作は, 普通の $+$ でOKです.

	# 入力
	S = []
	for _ in range(3):
	S.append(input())
	T = input()

	# 答えとなる文字列を作成
	ans = ""
	for i in range(len(T)):
	ans += S[int(T[i]) - 1]

	# 出力
	print(ans)

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

C - Neo-lexicographic Ordering

sortにkeyを渡す方法

リストのsortメソッドやsorted()関数では, 引数keyに関数などを指定することができます. 例えば, key=absと設定すれば, 絶対値にした上でソートされることになります.

今回の場合keyには, ある文字列を引数にとり, 通常の辞書順で対応する文字に置き換える関数を指定します. 例えば, $X =$ bacdefghijklmnopqrstuvwxzyならば, abxはbaxに置き換わります.

与えられた新しい辞書順と従来の辞書順の対応付けは, dict型を用いると便利です. キーのリストと値のリストから辞書を作成するには, 複数のリストなどの要素をまとめる関数であるzip()を用いることができます.

	import string

	# それまでに指定されている辞書dic_ruleに従って、文字列s_parを変換する関数
	def strings_change(s_par):
	s_change = ""
	for s in s_par:
	s_change += dic_rule[s]
	return s_change

	# 入力
	X = input()
	N = int(input())
	S = []
	for _ in range(N):
	S.append(input())

	# 辞書順をdict型に
	# 与えられた辞書順を本来の辞書順と対応付ける
	dic_keys = [x for x in X]
	dic_values = list(string.ascii_lowercase)
	dic_rule = dict(zip(dic_keys, dic_values))

	# sortメソッドにkeyを指定した上でソート
	S.sort(key=strings_change)

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

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

なんなら自分でソートしてやる方法(1)

やろうと思えば, 自分でソートすることができないわけではありません.

良く知られているソートアルゴリズムの1つに, バブルソート(bubble sort)があります.

リスト $S = [S_{1}, S_{2}, \dots, S_{N}]$ が与えられたときに, $S_{1}$ と $S_{2}$ を比べて $S_{1} < S_{2}$ となるように, $S_{2}$ と $S_{3}$ を比べて $S_{2} < S_{3}$ となるようにしていきます. 最後に, $S_{N - 1}$ と $S_{N}$ を比べて $S_{N - 1} < S_{N}$ となるようにすることで, 最終的に $S_{N}$ はその中で最も大きい要素になります.

これを再び繰り返します. $S_{1}$ と $S_{2}$ を比べて $S_{1} < S_{2}$ となるように, $S_{2}$ と $S_{3}$ を比べて $S_{2} < S_{3}$ となるようにしていきます. 最後に, $S_{N - 2}$ と $S_{N - 1}$ を比べて $S_{N - 2} < S_{N - 1}$ となるようにすることで, 最終的に $S_{N - 1}$ はその中で最も大きい要素になります.

これを最後まで繰り返せば, ソートが完了するというわけです.

図バブルソートの概念図. これを繰り返すことによってソートする.

しかしながら, 計算量は $O (N^{2})$ かかってしまう方法なので, さすがにTLEです.

	# 異なる文字列a_par, b_parを比較して、
	# a_parの方が辞書順に先ならばTrue、後ならばFalseを返す関数
	def left_large_judge(a_par, b_par, dic_rule_par):
	# 先頭から文字を比較していって、違う文字が出たらその辞書順を比較する
	for i in range(min(len(a_par), len(b_par))):
	if a_par[i] != b_par[i]:
	return dic_rule_par[a_par[i]] > dic_rule_par[b_par[i]]
	# 比較できる最後まで同じなら、文字数で比較する
	return len(a_par) > len(b_par)

	# 入力
	X = input()
	N = int(input())
	S = []
	for _ in range(N):
	S.append(input())

	# 辞書順をdict型に
	dic_keys = [x for x in X]
	dic_values = [i for i in range(len(X))]
	dic_rule = dict(zip(dic_keys, dic_values))

	# バブルソートを実行
	for j in range(1, N):
	for i in range(N - j):
	# 右の方(indexが大きい方)が辞書順で後になるようにしたい
	# 左の方(indexが小さい方)が辞書順で後の場合には入れ替えを行う
	if left_large_judge(S[i], S[i + 1], dic_rule):
	temp3 = S[i + 1]
	S[i + 1] = S[i]
	S[i] = temp3

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

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

なんなら自分でソートしてやる方法(2)

比較的計算量が少ないソートアルゴリズムの1つに, マージソート(marge sort)があります.

あらかじめソートしてある2つのリストを合体させて, ソートされた新しいリストを得ることは難しくありません. それぞれのリストの先頭を比較して, 辞書順で小さい方を新リストに加えるという操作を繰り返せばよいだけです. これを利用したのが, マージソートになります.

マージソートは, 分割するフェーズと合体するフェーズの2つに分かれます. 分割するフェーズでは, 多くの場合, ほぼ2分割されるように分解していきます. 最終的にそれぞれ1つの要素しか含まないように分割した後に, それらを順に合体していきます(1つの要素しか含まないリストは, すでにソートされていると見なせます).

図マージソートの概念図. 分割しまくった後, それらを互いにソートしつつ合体させていく.

分割や合体の回数が $O (\log N)$ で, それぞれの分割や合体自体には最大で $O (N)$ かかるので, 必要な計算量は $O (N \log N)$ となります. これならACです.

	from collections import deque

	# 異なる文字列a_par, b_parを比較して、
	# a_parの方が辞書順に先ならばTrue、後ならばFalseを返す関数
	def left_small_judge(a_par, b_par, dic_rule_par):
	# 先頭から文字を比較していって、違う文字が出たらその辞書順を比較する
	for i in range(min(len(a_par), len(b_par))):
	if a_par[i] != b_par[i]:
	return dic_rule_par[a_par[i]] < dic_rule_par[b_par[i]]
	# 比較できる最後まで同じなら、文字数で比較する
	return len(a_par) < len(b_par)

	# 異なる2つの文字列グループを、辞書順に併合したものを返す関数
	# 各文字列グループはすでに辞書順に並んでいる(か、1文字列である)必要がある
	def two_str_marge(a_par, b_par, dic_rule_par):
	# popleftしたいので、deque型に変換
	a_par_deque = deque(a_par)
	b_par_deque = deque(b_par)
	# 返す文字列グループを格納するリスト
	temp4 = deque()
	# 文字列グループのどちらかが消えるまで、
	# 各文字列グループの先頭の文字列を比較して、temp4に加え続ける
	while a_par_deque and b_par_deque:
	if left_small_judge(a_par_deque[0], b_par_deque[0], dic_rule_par):
	temp4.append(a_par_deque.popleft())
	else:
	temp4.append(b_par_deque.popleft())
	# どちらかの文字列グループが生き残るので、それを最後にtemp4にくっつける
	temp4 += a_par_deque + b_par_deque
	# temp4を返す
	return list(temp4)

	# 文字列グループs_parを2つに分割し続ける、
	# 1文字列になったらそれらをtwo_str_margeで併合し続ける再帰関数
	def marge_sort(s_par, dic_rule_par):
	# 1文字以上なら、分割作業
	if len(s_par) > 1:
	return two_str_marge(marge_sort(s_par[:len(s_par) // 2], dic_rule_par), marge_sort(s_par[len(s_par) // 2:], dic_rule_par), dic_rule_par)
	# 1文字ならそのまま文字列を返し、two_str_margeへつなげる
	else:
	return s_par

	# 入力
	X = input()
	N = int(input())
	S = []
	for _ in range(N):
	S.append(input())

	# 辞書順をdict型に
	dic_keys = [x for x in X]
	dic_values = [i for i in range(len(X))]
	dic_rule = dict(zip(dic_keys, dic_values))

	# marge_sortでソートする
	S_sorted = marge_sort(S, dic_rule)

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

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

D - Strange Lunchbox

動的計画法(dynamic programming)を用いて解くことを考えます.

動的計画法を用いて計算する量 $dp [i] [j] [k]$ として, 以下の量を考えます.

$i$ 種類目までの弁当を購入するか否かを決定したときに, $j$ 個のたこ焼きと $k$ 個のたい焼きを購入するために買うべき弁当の個数の最小値

$0$ 種類目までの弁当を購入するか否かを決定したときに, $0$ 個のたこ焼きと $0$ 個のたい焼きを購入するために買うべき弁当の個数の最小値は当然 $0$ なので, 初期値として $dp [0] [0] [0] = 0$ としておきます.

$dp [i] [j] [k]$ が正しく入力されているとき, $i + 1$ 番目の弁当を買うか買わないかの選択とすることができます.

買う場合：新たに $A [i]$ 個のたこ焼きと $B [i]$ 個のたい焼きを獲得することになります.
$dp [i + 1] [min (j + A [i], X)] [min (k + B [i], Y)]$ を $dp [i] [j] [k] + 1$ で更新します(小さい方の値にする).
買わない場合：新たにたこ焼きやたい焼きは増えません.
$dp [i + 1] [j] [k]$ を $dp [i] [j] [k]$ で更新します(小さい方の値にする).

$dp [i] [j] [k]$ が正しく入力されていない(適切な初期値のままの)場合は, $i$ 種類目までの弁当を購入するか否かを決定していくプロセスでは, $j$ 個のたこ焼きと $k$ 個のたい焼きを獲得することができないということになるので, そのままにしておきます.

最後に出力すべきなのは, $dp [N] [X] [Y]$ になります. 初期値のままの場合は $- 1$ を出力することに注意してください.

初期値については, 例えば $N + 1$ ( $N + 1$ 個以上の弁当を買うことにはなりません)などが適切でしょう.

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

	# dp[i][j][k]で「i種類目までの弁当を購入するか否かを決定したときに、
	# j個のたこ焼きとk個のたい焼きを購入するために、
	# 買うべき弁当の個数の最小値」を計算していく

	# 初期値はN + 1を記録しておく
	dp = [[[N + 1 for _ in range(Y + 1)] for _ in range(X + 1)] for _ in range(N + 1)]

	# 「0種類目までの弁当を購入するか否かを決定したときに、
	# 0個のたこ焼きと0個のたい焼きを購入するために、
	# 買うべき弁当の個数の最小値」は当然0
	dp[0][0][0] = 0

	# dp[i][j][k]が正しく入力されているとき、
	# i + 1番目の弁当を……
	# 1) 買う⇒新たにA[i]個のたこ焼きとB[i]個のたい焼きを獲得する
	# dp[i + 1][min(j + A[i], X)][min(k + B[i], Y)]をdp[i][j][k] + 1で更新
	# 2) 買わない⇒新たにたこ焼きやたい焼きは増えない
	# dp[i + 1][j][k]をdp[i][j][k]で更新

	for i in range(N):
	A_i, B_i = [int(x) for x in input().split()]
	for j in range(X + 1):
	for k in range(Y + 1):
	# この時点でdp[i][j][k] = N + 1ならば、
	# i種類目までの弁当を購入するか否かを決定するプロセスでは
	# j個のたこ焼きとk個のたい焼きは購入できない
	if dp[i][j][k] < N + 1:
	dp[i + 1][min(j + A_i, X)][min(k + B_i, Y)] = min(dp[i + 1][min(j + A_i, X)][min(k + B_i, Y)], dp[i][j][k] + 1)
	dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k])

	# 出力(dp[N][X][Y])
	if dp[N][X][Y] < N + 1:
	print(dp[N][X][Y])
	else:
	print(-1)

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

E以降

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

参考にしたサイト等

「解説 - サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）」
Editorial - Sciseed Programming Contest 2021（AtCoder Beginner Contest 219）
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
nkmk様による「Pythonのsorted()やmax()などで引数keyを指定」
Pythonのsorted()やmax()などで引数keyを指定 | note.nkmk.me
Pythonの組み込み関数sorted()やmax(), min(), リストのsort()メソッドなどでは, 引数keyに呼び出し可能オブジェクトを指定できる. これにより, 要素に何らかの処理を行った結果を元にソートしたり最大値・最小値を取得したりできる. ソート HOW TO - Key 関数 — Python 3.8.6rc1 ドキュメントここでは, 以下の内容につい...
nkmk様による「Pythonで辞書を作成するdict()と波括弧, 辞書内包表記」
Pythonで辞書を作成するdict()と波括弧, 辞書内包表記 | note.nkmk.me
Pythonで辞書（dict型オブジェクト）を作成するには様々な方法がある. キーkeyと値valueを一つずつ設定するだけでなく, リストから辞書を作成することも可能. ここでは以下の内容について説明する. 波括弧{}で辞書を作成キーと値を個別に指定複数の辞書を結合（マージ）キーと値を個別に指定複数の辞書を結合（マージ） d...
増井敏克様, 渡部拓也様による「Pythonでアルゴリズムに入門する！押さえておきたい二分探索とバブルソートとは？」(CodeZine)
Pythonでアルゴリズムに入門する！押さえておきたい二分探索とバブルソートとは？
　プログラムを軽く効率的にするために不可欠なアルゴリズム. 翔泳社から発売中の『Pythonではじめるアルゴリズム入門』では, 人気が高くユーザーも増えているPythonを用い, 探索やソートなど基本的なアルゴリズムを解説しています. CodeZineでは以前, 線形探索と選択ソートを紹介しましたが, 今回は新たに二分探索とバブルソートを紹介します.
渕田孝康様による「バブルソート | いろいろなソートアルゴリズム」(http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/bubble-sort.html)
渕田孝康様による「マージソート | いろいろなソートアルゴリズム」(http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/marge-sort.html)

サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）をPythonで解く

A - AtCoder Quiz 2

B - Maritozzo

C - Neo-lexicographic Ordering

sortにkeyを渡す方法

なんなら自分でソートしてやる方法(1)

なんなら自分でソートしてやる方法(2)

D - Strange Lunchbox

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