[ABC304 Python]東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）A～D問題Python解説

A問題

A - First Player

# 入力
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問題

B - Subscribers

# 入力
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問題

C - Virus

# インポート
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問題

D - A Piece of Cake

# インポート
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になっているので、
イチゴが載っていないピースがある場合は別に求めてあげましょう。