東京海上日動プログラミングコンテスト2023(AtCoder Beginner Contest 299)をPythonで解く-Shinoryo's Weblog

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

こんにちは, Shinoryoです.

今回は東京海上日動プログラミングコンテスト2023(AtCoder Beginner Contest 299)を, Pythonで解いてみた結果を書き連ねていこうと思います.

1A - Treasure Chest
2B - Trick Taking
3C - Dango
4D - Find by Query
5E以降
6参考にしたサイト等

A - Treasure Chest

|の位置と*の位置を取得し, その大小関係をもとに判断すればよいです. |は2つあるので, 左側のものはfindメソッドで, 右側のものはrfindメソッドで検索します.

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

	# \|と*を探す
	tatebou_first = S.find("\|")
	tatebou_second = S.rfind("\|")
	ast_first = S.find("*")

	# \|と*の位置の大小関係をもとに出力
	if tatebou_first < ast_first and ast_first < tatebou_second:
	print("in")
	else:
	print("out")

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

B - Trick Taking

以下のステップに分けて考えるとよいでしょう.

勝者になりうるカードの色 $A$ を調べる.
色が $A$ のカードの中で, 最も大きい値のカードを調べる.

勝者になりうるカードの色 $A$ は, 数値 $T$ と配列 $C$ の比較で調べることができます. $C$ に $T$ が含まれれば $A = T$ , $C$ に $T$ が含まれなければ $A = C_{1}$ です.

その後, カードを一つひとつ調べていって, カードの色が $A$ であれば最大判定に加えればよいです.

	# 入力
	N, T = list(map(int, input().split()))
	C = list(map(int, input().split()))
	R = list(map(int, input().split()))

	# ルールに従って判断
	# 勝負となるカードの色Aを決める
	if T in C:
	A = T
	else:
	A = C[0]

	# カードの色がAであるもののうち、最も大きい人を探す
	ans_index = 0
	ans_num = 0
	for i in range(N):
	if C[i] == A:
	if ans_num < R[i]:
	ans_index = i
	ans_num = R[i]

	# 出力
	print(ans_index + 1)

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

C - Dango

oと-が両方含まれているかどうかで区別すると, この問題は非常に簡単になります.

両方含まれていれば, oが連続している数の最大が答えになります.
いずれかが含まれていなければ, $S$ はダンゴ文字列になりえないので $- 1$ が答えになります.

oが連続している数を調べるには, $S$ を-で分割してみればよいです. S.split("-")とすることで, ["ooo", "o","oooo","oo","ooooo", ...]のように, oが連続している部分を取り出すことができます. それぞれの要素に対してlen関数を適用したものの最大値をとれば, 答えが分かります.

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

	# oと-が両方含まれているかどうかで区別する
	if "o" in S and "-" in S:
	# 含まれていれば、oが連続している数の最大が答えになる
	print(max(map(len, S.split("-"))))
	else:
	# どちらかが含まれていなければダンゴ文字列にならない
	print(-1)

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

D - Find by Query

二分探索のようにして探していけばよいでしょう. 例えば, $N = 7$ , $S = 0010011$ というパターンを考えます. すると, 以下のようにしていくことで効率よく探せることが分かります.

$l = 1$ , $r = 7$ とします.
$m = (l + r) / 2 = 4$ とします.
$S_{m} = S_{4}$ の値を調べます.
$S_{m} = S_{4} = 0$ なので, $l = 4$ と更新します.
$m = (l + r) / 2 = 5$ とします(小数点以下は切り捨てます).
$S_{m} = S_{5}$ の値を調べます.
$S_{m} = S_{5} = 0$ なので, $l = 5$ と更新します.
$m = (l + r) / 2 = 6$ とします.
$S_{m} = S_{6}$ の値を調べます.
$S_{m} = S_{4} = 1$ なので, $r = 6$ と更新します.
$l = 5$ , $r = 6$ より $l + 1 = r$ となったので, $l = 5$ を出力して終了します.

このように, $S_{l} = 0$ , $S_{r} = 1$ の条件のもとで少しずつ $l$ と $r$ の差を縮めていって, $l + 1 = r$ となったときに, $l$ が求める答えとなるようにします. $l$ と $r$ の真ん中の値 $m$ を計算して $S_{m}$ の値を取得して $l$ または $r$ の値を更新するのを $1$ ループとすれば, 高々 $\log N$ ループで $l + 1 = r$ となります. $N \leq 2 \times 10^{5}$ なので, 高々 $18$ ループで $l + 1 = r$ となります.

	# 入力
	N = int(input())

	# 二分探索で見つける
	# 最初はleft = 0、right = N - 1
	left = 1
	right = N

	# 限界20回なので一応20回ループ
	for _ in range(20):
	# 真ん中のindexのSを尋ねる
	mid = (left + right) // 2
	print("? " + str(mid))
	# S_midが0なら、leftをmidにする
	if int(input()) == 0:
	left = mid
	# S_midが1なら、rightをmidにする
	else:
	right = mid
	# leftとrightの差が1なら、ちょうどそこで0から1になっているので、それを出力
	if left + 1 == right:
	print("! " + str(left))
	exit()

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

E以降

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

参考にしたサイト等

「解説 - 東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 299）」
Editorial - Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 299)
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()メソッドを使う. 標準ライブラリのreモジュールを使うと正規表現でより柔軟な処理が可能. 特定の文字列を含むか判定: in演算子特定の文字列の位置を取得: find(), rfind()find()rfind()index(), rindex() find() rfin...
nkmk様による「Pythonで文字列を分割（区切り文字, 改行, 正規表現, 文字数）」
Pythonで文字列を分割（区切り文字, 改行, 正規表現, 文字数） | note.nkmk.me
Pythonの文字列を区切り文字, 改行, 正規表現, 文字数で分割する方法を説明する. 区切り文字で分割: split() 区切り文字で右から分割: rsplit() 改行で分割: splitlines() 正規表現にマッチした部分で分割: re.split()複数の異なる区切り文字で分割複数の異なる区切り文字で分割文字列のリストを連結文字数で分割: スラ...

東京海上日動プログラミングコンテスト2023(AtCoder Beginner Contest 299)をPythonで解く

A - Treasure Chest

B - Trick Taking

C - Dango

D - Find by Query

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