トヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)をPythonで解く-Shinoryo's Weblog

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

こんにちは, Shinoryoです.

今回はトヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)を, Pythonで解いてみた結果を書き連ねていこうと思います.

1A - Attack
2B - Find snuke
3C - Almost Equal
4D - Impartial Gift
5E以降
6参考にしたサイト等

A - Attack

$1 \leq A, B \leq 10^{18}$ のため, 通常のPythonで用いられているfloat型だと精度が足りずWAになってしまいます. (ここでは, 切り上げにはmath.ceil()を用いています. )

	import math

	A, B = list(map(int, input().split()))
	print(math.ceil(A / B))

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

解決方法としては, あくまでも整数の範囲で計算をする方法です. 例えば, $A$ が $B$ で割り切れれば $A / B$ の切り捨て, 割り切れなければ $(A / B)$ の切り捨てに $+ 1$ したものを出力すればよいことが分かります.

	A, B = list(map(int, input().split()))
	if A % B == 0:
	print(A // B)
	else:
	print(A // B + 1)

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

あるいは, numpyを用いて浮動小数点型の精度を高める方法もあります. 四倍精度浮動小数点型だと仮数部が112ビットありますので, 十分に対応することができます.

	import numpy as np

	A_B_numpy = np.array(list(map(int, input().split())), dtype=np.float128)
	print(np.ceil(np.array([A_B_numpy[0] / A_B_numpy[1]])).astype(np.int64)[0])

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

B - Find snuke

B問題にしては面食らう感じにはなりますが, 結局は全ての文字列のパターンを調べることになるようです.

あるマス $(i, j)$ に焦点を当てます. そのマスを1文字目とする調べるべき文字列は, そのマスから縦・横・斜めに伸びる5文字の文字列になります. それらの文字列が「snuke」に一致するかどうかを順番に調べていくのです.

これを全てのマスに対して繰り返していけばよいです. 縦・横・斜めに伸びる5文字の文字列を調べる際にインデックスエラーを起こさないように注意しましょう.

	# 入力
	H, W = list(map(int, input().split()))
	S = []
	for _ in range(H):
	S.append(list(input()))

	# 上下左右斜めの方向を表すリスト
	dx = [-1,-1,-1,0,0,1,1,1]
	dy = [-1,0,1,-1,1,-1,0,1]

	# 各マスに対してループ
	for i in range(H):
	for j in range(W):
	# 各方向に対してループ
	for k in range(8):
	# 文字列を取得
	string = ""
	for l in range(5):
	x = i + l * dx[k]
	y = j + l * dy[k]
	# indexエラー回避
	if x > -1 and x < H and y > -1 and y < W:
	string += S[x][y]
	else:
	break
	# 文字列がsnukeなら、座標一覧を出力してexit
	if string == "snuke":
	for l in range(5):
	x = i + l * dx[k]
	y = j + l * dy[k]
	print(x + 1, y + 1)
	exit()

	# 必ずsnukeは存在するので、ここに来ることはない

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

C - Almost Equal

$S_{i}$ を並べ替えた全てのパターンに対して, 条件を満たすかを確かめていけばよいです.

$S_{i}$ を並べ替えたものを $T_{i}$ として, $T_{1}$ と $T_{2}$ , $T_{2}$ と $T_{3}$ , ……を比較していって, 2箇所以上異なっている組み合わせがある場合には条件を満たさないことが分かるので, それを実装します.

	import itertools

	# 入力
	N, M = list(map(int, input().split()))
	S = []
	for _ in range(N):
	S.append(input())

	# Sを並べ替えたものでループ
	for T in itertools.permutations(S, N):
	ok = True
	# T_iとT_(i + 1)が2箇所以上異なっていたら条件を満たさない
	for i in range(N - 1):
	if sum(T[i][j] != T[i + 1][j] for j in range(M)) > 1:
	ok = False
	# ok == Trueなら、そのTは条件を満たす
	if ok:
	print("Yes")
	exit()

	# ここまできたら、条件を満たすTは存在しない
	print("No")

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

D - Impartial Gift

公式解説の通りに実装すればよいです.

基本的には, なるべく $A$ と $B$ のそれぞれ最大値をとりたいのですが, それで差が $D$ 以内にならない場合には, $A$ の最大値と $B$ の最大値のどちらか大きい方を削除することで, 次の可能性を探ります. ( $A$ の最大値と $B$ の最大値のどちらか小さい方を削除してしまうと, それらの差はますます広まってしまいます. )

Pythonで実装する際には, リストからの削除を.pop()などで実装すると, 時間計算量が多くTLEとなってしまいます.

	# 入力
	N, M, D = list(map(int, input().split()))
	A = sorted(list(map(int, input().split())), reverse=True)
	B = sorted(list(map(int, input().split())), reverse=True)

	# AかBが空集合になるまでループ
	while len(A) > 0 and len(B) > 0:
	# Aの最大値とBの最大値の差がD以内なら、適切な出力をし終了
	if abs(A[0] - B[0]) <= D:
	print(A[0] + B[0])
	exit()
	# そうでないなら、Aの最大値とBの最大値の大きい方を消去する
	else:
	if A[0] > B[0]:
	A.pop(0)
	else:
	B.pop(0)

	# ここまできたら、適切な組み合わせが存在しないことになる
	print(-1)

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

例えば, 以下の対応が必要になります.

collectionsモジュールのdeque型を用いて, 先頭・末尾の要素を追加・削除するのにかかる時間計算量を減らす.
先頭の要素を削除する代わりに, 注目する要素を一つ後ろにずらす.

1番目の方法を用いたコードです.

	from collections import deque

	# 入力
	N, M, D = list(map(int, input().split()))
	A = deque(sorted(list(map(int, input().split())), reverse=True))
	B = deque(sorted(list(map(int, input().split())), reverse=True))

	# AかBが空集合になるまでループ
	while len(A) > 0 and len(B) > 0:
	# Aの最大値とBの最大値の差がD以内なら、適切な出力をし終了
	if abs(A[0] - B[0]) <= D:
	print(A[0] + B[0])
	exit()
	# そうでないなら、Aの最大値とBの最大値の大きい方を消去する
	else:
	if A[0] > B[0]:
	A.popleft()
	else:
	B.popleft()

	# ここまできたら、適切な組み合わせが存在しないことになる
	print(-1)

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

2番目の方法を用いたコードです.

	# 入力
	N, M, D = list(map(int, input().split()))
	A = sorted(list(map(int, input().split())), reverse=True)
	B = sorted(list(map(int, input().split())), reverse=True)

	# AとBの要素を削除していく代わりに、
	# AとBの要素をインデックス0から参照していくことにする
	# 右端まで到達するまでループ
	i = 0
	j = 0
	while i < N and j < M:
	# Aの最大値とBの最大値の差がD以内なら、適切な出力をし終了
	if abs(A[i] - B[j]) <= D:
	print(A[i] + B[j])
	exit()
	# そうでないなら、Aの最大値とBの最大値の大きい方を消去する
	else:
	if A[i] > B[j]:
	i += 1
	else:
	j += 1

	# ここまできたら、適切な組み合わせが存在しないことになる
	print(-1)

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

E以降

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

参考にしたサイト等

「解説 - トヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)」
Editorial - TOYOTA MOTOR CORPORATION Programming Contest 2023#2 (AtCoder Beginner Contest 302)
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
nkmk様による「NumPyのデータ型dtype一覧とastypeによる変換（キャスト）」
NumPyのデータ型dtype一覧とastypeによる変換（キャスト） | note.nkmk.me
NumPy配列ndarrayはデータ型dtypeを保持しており, np.array()でndarrayオブジェクトを生成する際に指定したり, astype()メソッドで変更したりすることができる. Data type objects (dtype) — NumPy v1.21 Manual numpy.ndarray.astype — NumPy v1.21 Manual 基本的には一つのndarrayオブジェクトに対して一つのdtypeが設...
nkmk様による「Pythonのdequeでキュー, スタック, デック（両端キュー）を扱う」
Pythonのdequeでキュー, スタック, デック（両端キュー）を扱う | note.nkmk.me
Pythonの標準ライブラリcollectionsモジュールのdeque型を使うと, データをキューやスタック, デック（両端キュー）として効率的に扱うことができる. collections.deque --- コンテナデータ型 — Python 3.7.3 ドキュメント組み込みのリストlistをキューやスタック, デック（両端キュー）として使うことも可能だが, リスト...

トヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)をPythonで解く

A - Attack

B - Find snuke

C - Almost Equal

D - Impartial Gift

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