パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）をPythonで解く-Shinoryo's Weblog

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

こんにちは, Shinoryoです.

今回はパナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）を, Pythonで解いてみた結果を書き連ねていこうと思います.

1A - N-choice question
2B - Fill the Gaps
3C - AtCoder Cards
4D - Bitmask
5E以降
6参考にしたサイト等

A - N-choice question

先に $⌈ N / 2 ⌉$ 回勝利した方が勝利になります. 高橋くんと青木くんのそれぞれが勝った回数をfor文で調べていき, どちらかが $⌈ N / 2 ⌉$ 回勝利した時点でその人を出力して終了すればよいです.

Pythonにおける切り上げは, math.ceilで簡単に得ることができます.

	import math

	N = int(input())
	S = list(input())
	T_count = 0
	A_count = 0
	for i in range(N):
	if S[i] == "T":
	T_count += 1
	else:
	A_count += 1
	if T_count >= math.ceil(N / 2):
	print("T")
	exit()
	elif A_count >= math.ceil(N / 2):
	print("A")
	exit()

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

B - Fill the Gaps

基本的には $A_{1}, A_{2}, \dots, A_{N}$ をそのまま出力し, もし途中で $| A_{i} - A_{i + 1} | \neq 1$ となった場合にはその間を埋めるように出力すればよいことが分かります. Pythonのprint()は最後にデフォルトで改行を加えてしまうため, print(end = " ")のように最後に改行ではなく空白を加えるようにします.

	# 入力
	N = int(input())
	A = list(map(int, input().split()))

	# 隣接する2項の差を計算していく
	for i in range(N - 1):
	# 1ならそのまま出力する
	if abs(A[i] - A[i + 1]) == 1:
	print(A[i], end = " ")
	# 1でなければ、その間を埋めるように出力する
	else:
	if A[i] < A[i + 1]:
	print(" ".join(list(map(str, range(A[i], A[i + 1], 1)))), end = " ")
	else:
	print(" ".join(list(map(str, range(A[i], A[i + 1], -1)))), end = " ")
	print(A[-1])

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

C - AtCoder Cards

順番に $S$ に含まれている文字が $T$ にも含まれているかを確認する.
- $S$ に含まれている文字が $T$ にも含まれていればとりあえずOK. その文字を使うことにして, $T$ からその文字を消す.
- $S$ に含まれている文字が $T$ に含まれていれなければ, $T$ に@が含まれているかを確認する. $T$ に@が含まれていれば, その文字を使うことにして, $T$ からその文字を消す.
- $S$ に@が含まれていれば, それは $T$ における「余り物の」a, t, c, o, d, e, rあるいは@と対応させたいので, 個数を記録して保留にする.
$S$ に含まれている@の個数分, $T$ に「余り物の」a, t, c, o, d, e, rあるいは@が存在するかを調べる. 存在すれば, その文字を使うことにして, $T$ からその文字を消す.

以上を通過したらYes, どこかの段階で条件から外れたらNoを出力する.

ミソなのは, 「 $S$ に含まれている文字が $T$ にも含まれてい」るといったことを確認する手段です.

すでに使った文字が消去された新しい $T$ を用いて検索をしなければなりません. しかし, ここにリストに対するinを使っていた場合, inの時間計算量は $O (N)$ ( $N$ はリストの要素数)であるため, 結果としてTLEになってしまいます.

	# 入力
	S = list(input())
	T = list(input())

	# 順番にSにある文字列がTにあるかどうかを調べる
	# なかったら"@"で対応できる
	# Sに"@"が含まれていたら対応するのはなんでもいいので、ひとまず保留
	S_at_count = 0
	for i in range(len(S)):
	if S[i] == "@":
	S_at_count += 1
	elif S[i] in T:
	index = T.index(S[i])
	del T[index]
	elif S[i] in ["a", "t", "c", "o", "d", "e", "r"] and "@" in T:
	index = T.index("@")
	del T[index]
	else:
	print("No")
	exit()

	# Sに"@"が含まれている数分、Tに対応するものがあるかを調べる
	for i in range(S_at_count):
	if "a" in T:
	index = T.index("a")
	del T[index]
	elif "t" in T:
	index = T.index("t")
	del T[index]
	elif "c" in T:
	index = T.index("c")
	del T[index]
	elif "o" in T:
	index = T.index("o")
	del T[index]
	elif "d" in T:
	index = T.index("d")
	del T[index]
	elif "e" in T:
	index = T.index("e")
	del T[index]
	elif "r" in T:
	index = T.index("r")
	del T[index]
	elif "@" in T:
	index = T.index("@")
	del T[index]
	else:
	print("No")
	exit()

	# ここまで残っていたら"Yes"を出力
	print("Yes")

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

これは, 文字列 $T$ の情報を, 「文字 $x$ が $y$ 個含まれている」といった情報に変換することです. これを辞書型で実装すれば, inの時間計算量は $O (1)$ で済みます. 「 $T$ から文字 $x$ を消す」は $y$ を $1$ 減らせばよく, $y$ が $0$ の場合は文字 $x$ が $T$ に含まれていないものとみなすことにします.

「文字 $x$ が $y$ 個含まれている」といった情報への変換は, collections.Counterを用いると簡単に実装できます.

	from collections import Counter

	# 入力
	S = list(input())
	T = list(input())
	S_Counter = Counter(S)
	T_Counter = Counter(T)
	S_set = set(S)
	T_set = set(T)

	# 順番にSにある文字列がTにあるかどうかを調べる
	# なかったら"@"で対応できる
	# Sに"@"が含まれていたら対応するのはなんでもいいので、ひとまず保留
	S_at_count = 0
	for i in range(len(S)):
	if S[i] == "@":
	S_at_count += 1
	elif S[i] in T_set and T_Counter[S[i]] > 0:
	T_Counter[S[i]] -= 1
	elif S[i] in ["a", "t", "c", "o", "d", "e", "r"] and "@" in T_set and T_Counter["@"] > 0:
	T_Counter["@"] -= 1
	else:
	print("No")
	exit()

	# Sに"@"が含まれている数分、Tに対応するものがあるかを調べる
	for i in range(S_at_count):
	if "a" in T_set and T_Counter["a"] > 0:
	T_Counter["a"] -= 1
	elif "t" in T_set and T_Counter["t"] > 0:
	T_Counter["t"] -= 1
	elif "c" in T_set and T_Counter["c"] > 0:
	T_Counter["c"] -= 1
	elif "o" in T_set and T_Counter["o"] > 0:
	T_Counter["o"] -= 1
	elif "d" in T_set and T_Counter["d"] > 0:
	T_Counter["d"] -= 1
	elif "e" in T_set and T_Counter["e"] > 0:
	T_Counter["e"] -= 1
	elif "r" in T_set and T_Counter["r"] > 0:
	T_Counter["r"] -= 1
	elif "@" in T_set and T_Counter["@"] > 0:
	T_Counter["@"] -= 1
	else:
	print("No")
	exit()

	# ここまで残っていたら"Yes"を出力
	print("Yes")

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

D - Bitmask

まず, 全ての?を $0$ に変えたものが, $T$ の最小値になります. これによりも $N$ が小さい場合, $- 1$ を出力することになります.

その条件をクリアしたら, $N$ を超えないように?を $1$ に変えていくことになります. $1$ に変えた?が左にあればあるほどその数字は大きくなりますので, 左の?から順に $1$ に変えて, $N$ を超えないかを確かめていくことになります.

2進法の文字列を10進法の整数に変えるには, int(文字列, 基数)を用います.

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

	# まずは"?"を"0"にしたものを考える
	# それがNより大きければ、これ以上小さくしようがないので-1を出力する
	S_all_0_bin = "".join(list("0" if s == "?" else s for s in S))
	ans = int(S_all_0_bin, 2)
	if ans > N:
	print(-1)
	else:
	# Nを超えないように、最初の"?"から順に"1"に置き換えていく
	for i in range(len(S)):
	if S[i] == "?":
	S_add_bin = "".join(list("1" if j == i else "0" for j in range(len(S))))
	S_add_dec = int(S_add_bin, 2)
	if ans + S_add_dec <= N:
	ans += S_add_dec
	print(ans)

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

E以降

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

参考にしたサイト等

「解説 - パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）」
Editorial - パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
nkmk様による「Pythonで小数点以下を切り捨て・切り上げ: math.floor(), math.ceil()」
Pythonで小数点以下を切り捨て・切り上げ: math.floor(), math.ceil() | note.nkmk.me
Pythonで浮動小数点数floatの小数点以下を切り捨て・切り上げするには, 標準ライブラリmathモジュールのfloor(), ceil()を使う. 小数点以下を切り捨て: math.floor() 小数点以下を切り上げ: math.ceil() math.floor()とint()との違い無限大への丸め (rounding toward infinity; RI) なお, 厳密にはmath.floor()は「負の無...
nkmk様による「PythonのCounterでリストの各要素の出現個数をカウント」
PythonのCounterでリストの各要素の出現個数をカウント | note.nkmk.me
Pythonでリストやタプルの全要素の個数は組み込み関数len(), 各要素の個数（要素ごとの出現回数）はcount()メソッドで取得できる. さらに, Python標準ライブラリcollectionsのCounterクラスを使うと, 出現回数が多い順に要素を取得できたりする. ここでは, 全要素数をカウント: len() 各要素の個数（要素ごとの出現回数）を...
nkmk様による「Pythonで2進数, 8進数, 16進数の数値・文字列を相互に変換」
Pythonで2進数, 8進数, 16進数の数値・文字列を相互に変換 | note.nkmk.me
Pythonでは通常の10進数だけでなく2進数, 8進数, 16進数として数値や文字列を扱うことができる. 相互に変換するのも簡単. ここでは, 以下の内容についてサンプルコードとともに説明する. 整数を2進数, 8進数, 16進数で記述数値を2進数, 8進数, 16進数表記の文字列に変換組み込み関数bin(), oct(), hex()組み込み関数format...

パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）をPythonで解く

A - N-choice question

B - Fill the Gaps

C - AtCoder Cards

D - Bitmask

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