[ABC305 Python]京セラプログラミングコンテスト2023(AtCoder Beginner Contest 305)A～D問題Python解説
A問題
# 入力
N = int(input())
# 髙橋君が通り過ぎた給水所の中で、
# 一番髙橋君に近い給水所
near_start = N//5*5
# 髙橋君がこれから通る予定の給水所の中で、
# 一番髙橋君に近い給水所
near_goal = (N//5+1)*5
# 髙橋君とそれぞれの給水所との距離を比較して、
# より近い給水所の場所を出力する
if N-near_start > near_goal-N:
print(near_start)
else:
print(near_goal)
最も近い給水所の候補は2か所あります。
これまでの給水所の中で一番近い給水所と
これからの給水所の中で一番近い給水所です。
B問題
# 入力
p, q = input().split()
# 直線状の距離を表すリスト
line = [3, 1, 4, 1, 5, 9]
# 点pと点qの場所を保存するリスト
point_place = []
# 点pと点qについて、
# A～Gをインデックスで表す
for point in p, q:
if point == "A":
point_place.append(0)
if point == "B":
point_place.append(1)
if point == "C":
point_place.append(2)
if point == "D":
point_place.append(3)
if point == "E":
point_place.append(4)
if point == "F":
point_place.append(5)
if point == "G":
point_place.append(6)
# 点pと点qは順不同なので、
# インデクスが小さい順に並べ替える
point_place.sort()
# 最後に点pと点qの距離の合計を出力する
print(sum(line[point_place[0]:point_place[1]]))
全てのパターンを記載してもいいのですが、
少し工夫できるところは工夫したほうがいいかもしれません。
点A～Gをインデックスで表すと、
距離の合計を容易に出力することができます。
C問題
# インポート
from collections import defaultdict
# 入力
H, W = map(int, input().split())
# クッキーが置かれているマスのx座標
cookie_x = []
# クッキーが置かれているマスのy座標
coolie_y = []
# 全てのマスについて、
# クッキーが置かれている=マスが"#"
# なマスの座標を保存する
for i in range(H):
S = list(input())
for j in range(W):
if S[j] == "#":
cookie_x.append(i)
coolie_y.append(j)
# 各x座標について、
# そのx座標に何枚のクッキーが置かれているかを保存する
# defaultdict
dx = defaultdict(int)
# cookie_xからx座標ごとにクッキーの枚数をまとめる
for i in cookie_x:
dx[i] += 1
# 各x座標について、
# そのx座標に何枚のクッキーが置かれているかを保存する
# defaultdict
dy = defaultdict(int)
# cookie_xからx座標ごとにクッキーの枚数をまとめる
for i in coolie_y:
dy[i] += 1
# dxの中のx座標の中で
# 1つだけ数が少ないx座標が存在するため
# それを答えとする
for i in dx:
if dx[i] == min(dx.values()):
X = i+1
# dyの中のy座標の中で
# 1つだけ数が少ないy座標が存在するため
# それを答えとする
for i in dy:
if dy[i] == min(dy.values()):
Y = i+1
print(X, Y)すぬけ君が食べたクッキーの場所は不自然に"."になっています。
クッキーのx座標とy座標を分けた形で保存すると、
それぞれ1つずつ足りない箇所があるという訳です。
D問題
# インポート
import bisect
# 入力
N = int(input())
A = list(map(int, input().split()))
# これまでの累積睡眠時間を保存
s = 0
# 記録を付けたときに、これまで何時間寝たかを保存するリスト
# 最初は0時に起床しているので、累積睡眠時間は0
sleeped = [0]
# N回の記録について、
for i in range(1, N):
# インデックスで表すと、奇数と偶数が逆になることに注意
if i%2 == 0:
# 偶数番目は起床時間を表しているので、
# この時間をA[i]とすると、
# 前回の起床時間はA[i-1]、
# よって、今回の睡眠時間は、
# A[i]-A[i-1]となる
# よって睡眠時間を累積睡眠時間に追加し、
# sllepedにも代入する
sleeped.append(s+A[i]-A[i-1])
s += A[i]-A[i-1]
else:
# 奇数番目は就寝時間を表しているので、
# 睡眠時間に変化がない
# よって、これまでの累積睡眠時間を代入する
sleeped.append(s)
# 入力
Q = int(input())
# 全ての質問に対して
for i in range(Q):
# 入力
l, r = map(int, input().split())
# <重要>
# 睡眠記録をつけ始めてからl分後からr分後までの累積睡眠時間
# = (睡眠記録をつけ始めてからr分後までの累積睡眠時間
# - 睡眠記録をつけ始めてからr分後までの累積睡眠時間)
# 入力された時間が睡眠記録のどこにあるのか確認
L = bisect.bisect_right(A, l)
R = bisect.bisect_right(A, r)
# L%2=0つまり、l分後が睡眠時間であるならば、
# 前回の就寝時間A[L-1]~今の時間lまでの就寝時間と
# これまでの累積睡眠時間の和が
# 睡眠記録をつけ始めてからl分間の累積睡眠時間
if L%2 == 0:
ltime = l-A[L-1]+sleeped[L-1]
# l分後が睡眠時間でなければ、
# これまでの累積睡眠時間が
# 睡眠記録をつけ始めてからl分間の累積睡眠時間
else:
ltime = sleeped[L]
# R%2=0つまり、r分後が睡眠時間であるならば、
# 前回の就寝時間A[R-1]~今の時間rまでの就寝時間と
# これまでの累積睡眠時間の和が
# 睡眠記録をつけ始めてからr分間の累積睡眠時間
if R%2 == 0:
rtime = r-A[R-1]+sleeped[R-1]
# r分後が睡眠時間でなければ、
# これまでの累積睡眠時間が
# 睡眠記録をつけ始めてからr分間の累積睡眠時間
else:
rtime = sleeped[R-1]
# 出力するのはl分後からr分後
print(rtime-ltime)
二分探索で時刻lとrを探します。
ABCでは頻出ですが、
l~rまでの合計を求める時に、
0~lまでの合計-0~rまでの合計として求めると、
計算量を削減することができるので、おすすめです。