[ABC304 Python]東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）A～D問題Python解説
A問題
# 入力
N = int(input())
# 年齢を保存するリスト
age = []
# 名前を保存するリスト
name = []
for i in range(N):
# 入力
S, A = input().split()
# Aだけ整数型
A = int(A)
age.append(A)
name.append(S)
# 最年少の場所をインデックスで保存
min_age_index = age.index(min(age))
for i in range(N):
# 時計回りに出力
print(name[(min_age_index+i)%N])
年齢と名前を別々に保存し、
年齢が最も小さい人を探し出し、
その人から時計回りで名前を出力します。
B問題
# 入力
N = int(input())
# 問題文の条件通り、分岐の上出力する
if N <= 10**3-1:
print(N)
elif N <= 10**4-1:
print(N//10*10)
elif N <= 10**5-1:
print(N//100*100)
elif N <= 10**6-1:
print(N//1000*1000)
elif N <= 10**7-1:
print(N//10000*10000)
elif N <= 10**8-1:
print(N//100000*100000)
elif N <= 10**9-1:
print(N//1000000*1000000)
問題文通りに条件分岐を構成します。
C問題
# インポート
from collections import defaultdict, deque
# 入力
N, D = map(int, input().split())
# 感染しているかどうか判定
judge = [False for _ in range(N)]
# 人1は既に感染
judge[0] = True
# 人の座標を保存するリスト
coordinate = []
for i in range(N):
X, Y = map(int, input().split())
coordinate.append([X, Y])
# D以内にいる人の番号を保存するリスト
d = defaultdict(list)
for i in range(N):
for j in range(N):
# 距離がD以下であれば、番号を保存
if (coordinate[i][0]-coordinate[j][0])**2+(coordinate[i][1]-coordinate[j][1])**2 <= D**2:
d[i].append(j)
# DFS
# 新しく感染した人を保存
D = deque()
# 人1(インデックスなので0)が観戦
D.append(0)
# 新しく感染した人がいる間
while D:
# 感染した人を取り出し
virus = D.popleft()
# 感染した人からの距離がD以内の人について
for viru in d[virus]:
# まだ感染していなければ
if not judge[viru]:
# 新たに感染した人に追加し
D.append(viru)
# 判定をTrueにする
judge[viru] = True
# 全ての人に対して感染したかどうかを判定し、出力する
for i in range(N):
if judge[i]:
print("Yes")
else:
print("No")
全部探索すると、TLEになります。
人iとの距離がD以内になる人をそれぞれ保存し、
後はDFSで解いていきます。
D問題
# インポート
from bisect import bisect
from collections import defaultdict
# 入力
W, H = map(int, input().split())
N = int(input())
# イチゴのx座標
P = []
# イチゴのy座標
Q = []
# イチゴの座標の入力と保存
for i in range(N):
p, q = map(int, input().split())
P.append(p)
Q.append(q)
# ケーキのx方向分割数
A = int(input())
# x方向分割場所
a = list(map(int, input().split()))
# ケーキのy方向分割数
B = int(input())
# y方向分割場所
b = list(map(int, input().split()))
# ピースごとのイチゴの個数を保存するdefaultdict
d = defaultdict(int)
# 全てのイチゴについて
for i in range(N):
# x方向に二分探索
x = bisect(a, P[i])
# y方向に二分探索
y = bisect(b, Q[i])
# 二分探索の値ごとにイチゴの個数をカウントアップ
d[(x, y)] += 1
# イチゴがあるピースと全ピースの値に違いがある
# ＝イチゴが載っていないピースがある
if len(d) != (A+1)*(B+1):
# 最小値=イチゴが載っていないピースがあるので、0
# 最大値=一番イチゴが多いピース
print(0, max(d.values()))
else:
# 最小値=一番イチゴが少ないピース
# 最大値=一番イチゴが多いピース
print(min(d.values()), max(d.values()))2023/06/05追記しました。
イチゴの座標とケーキを分割する直線を保存する必要がありますが、
これを2次元配列で保存すると、
最大で4*10**10となってしまうのでTLEの可能性があります。
ABCではよく出てきますが、
x方向とy方向で分けて保存することで、
それぞれ1次元配列で保存できるという手法があります。
また、x,yそれぞれについて、
イチゴの座標を二分探索で求めることで、
計算量を削減します。
最後にdefaultdictを使って、
ピースごとのイチゴの個数を保存することで、
最小値と最大値を求めることができます。
defaultdictは初期値が0になっているので、
イチゴが載っていないピースがある場合は別に求めてあげましょう。