京セラプログラミングコンテスト2023(AtCoder Beginner Contest 305)をPythonで解く-Shinoryo's Weblog

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

こんにちは, Shinoryoです.

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

1A - Water Station
2B - ABCDEFG
3C - Snuke the Cookie Picker
4D - Sleep Log
5E以降
6参考にしたサイト等

A - Water Station

スタート地点にある給水所を $0$ 番目とし, それ以降も含めて $i$ 番目の給水所というようにナンバリングします. すると, $N km$ 地点に一番近い給水所の番号は, $N / 5$ を四捨五入することによって得られます. 最後にその番号を $5$ 倍すれば, その給水所が何 $km$ 地点にあるかを求められます.

Pythonでは組み込み関数round()を用いることで, 四捨五入を行うことができます.

print(round(int(input()) / 5) * 5)

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

あるいは, 正数に対する四捨五入は, 「 $0.5$ を足して切り捨てる」というアルゴリズムによって得ることができます. これを利用すれば, 浮動小数点数演算による誤差を全く気にしなくてよくなります.

print(((int(input()) + 2) // 5) * 5)

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

B - ABCDEFG

今回の実装方針は, 以下のようになります.

隣り合う点同士の距離を格納した配列distanceを用意する.
配列distanceの $i$ 番目から $j$ 番目までのスライス, distance[i:j]を取得する.
- $i$ と $j$ は, 入力したアルファベット $p$ , $q$ に応じて適切な値にする.
distance[i:j]の合計を出力する.

$i$ と $j$ は, アルファベットA～Gを0～6に変換して取得すればよいです. 以下の例では, 文字列「ABCDEFG」からそのアルファベットを検索することによって取得しています.

	# 入力
	p, q = input().split()

	# 入力したアルファベットを数字に変換
	alphabet_list = "ABCDEFG"
	p = alphabet_list.index(p)
	q = alphabet_list.index(q)

	# 距離配列のmin番目から(max-1)番目までの合計を出力
	distance = [3,1,4,1,5,9]
	print(sum(distance[min(p, q):max(p, q)]))

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

C - Snuke the Cookie Picker

#の数の各行の行合計を考えてみます. すると, 「 $0$ 」「 $a$ 」「 $a - 1$ 」の3パターンに分かれます(ただし, $a$ は行合計の最大値). 問題文の条件より, 「 $a - 1$ 」のパターンは1行しか存在せず, その1行のどこかにすぬけ君がクッキーを取ったマスが存在することになります. 列に対しても同様であり, これによりすぬけ君がクッキーを取ったマスを求めることができます.

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

	# #の行合計・列合計を取得
	hash_count_H = [sum(S[i][j] == "#" for j in range(W)) for i in range(H)]
	hash_count_W = [sum(S[i][j] == "#" for i in range(H)) for j in range(W)]

	# #の行合計が、最大値よりも1少ない列が答えの行
	# 列に関しても同様
	hast_lack_H = hash_count_H.index(max(hash_count_H) - 1)
	hast_lack_W = hash_count_W.index(max(hash_count_W) - 1)
	print(hast_lack_H + 1, hast_lack_W + 1)

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

D - Sleep Log

以下の関数 $f (x)$ を求めることがキーになります.

$f (x)$ ：睡眠記録を取り始めてから $x$ 分後までに何分寝たか

この関数 $f (x)$ を用いれば, 各クエリに対して求める数は $f (r_{i}) - f (l_{i})$ であることが分かります.

$f (A_{i})$ のリストは, $i = 0$ から順々に計算していくことで求めることができます. そこから任意の $x$ に対する $f (x)$ は, 以下のようにして求めることができます.

$A_{j - 1} \leq x < A_{j}$ となる $j$ を探す.
$f (x)$ を以下の式によって求める: $\begin{array}{r} (1) & f (x) = f (A_{j - 1}) + (f (A_{j}) - f (A_{j - 1})) \times \frac{x - A_{j - 1}}{A_{j} - A_{j - 1}} . \end{array}$

なお, $f (A_{j}) - f (A_{j - 1})$ は $A_{j} - A_{j - 1}$ または $0$ のいずれかです. つまり, 式 $(1)$ を以下のように書き換えることができます: $\begin{aligned} (2) & f (x) & = {\begin{cases} f (A_{j - 1}) + (x - A_{j - 1}) & if f (A_{j}) - f (A_{j - 1}) > 0, \\ f (A_{j - 1}) & others . \end{cases} \end{aligned}$

	import bisect

	def func(x, A, A_accum):
	x_index = bisect.bisect(A, x)
	return A_accum[x_index - 1] + (A_accum[x_index] - A_accum[x_index - 1] > 0) * (x - A[x_index - 1])

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

	# A_accum[i] = f(A[i])
	# f(x)：睡眠記録を取り始めてからx分後までに何分寝たか
	A_accum = [0 for _ in range(N + 1)]
	for i in range(1, N):
	A_accum[i] = A_accum[i - 1] + (i % 2 == 0) * (A[i] - A[i - 1])
	A_accum[N] = A_accum[N - 1]

	# 各クエリに対してループ
	for _ in range(int(input())):
	# l, rの入力
	l, r = map(int, input().split())

	# 求めるのは、f(r) - f(l)
	print(func(r, A, A_accum) - func(l, A, A_accum))

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

E以降

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

参考にしたサイト等

「解説 - 京セラプログラミングコンテスト2023(AtCoder Beginner Contest 305)」
Editorial - KYOCERA Programming Contest 2023（AtCoder Beginner Contest 305）
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
Wakasugi Tatsuroh様による「Pythonで二分探索を行うライブラリ『bisect』」
Pythonで二分探索を行うライブラリ「bisect」 - Qiita
趣味で競プロをやるようになり, Atcoderの問題を何問か解いているのだが, やっている内に覚えないといけないこともいくつかあるわけで. その内の一つに二分探索というアルゴリズムを使うという場面を多…

京セラプログラミングコンテスト2023(AtCoder Beginner Contest 305)をPythonで解く

A - Water Station

B - ABCDEFG

C - Snuke the Cookie Picker

D - Sleep Log

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