今回はPythonでABC428をABCEまで解くことができたので、その備忘録を纏めます。
コンテスト概要
AtCoder Beginner Contest 428
開催日:2025年10月18日 21:30-22:40
A - Grandma's Footsteps
この問題は「走って止まるを繰り返す高橋君が、X秒後にどれくらい進んでいるか」を求めるシンプルなシミュレーション問題
1. 1サイクルの長さを求める → 「走るA秒＋止まるB秒」で cycle = A + B
2. X秒の中に何サイクル分あるかを求める → full = X // cycle （整数のわり算）
3. 余った時間（サイクル途中の時間を求める → remain = X % cycle
4. 走っている時間の合計を計算
・完全なサイクル分：A × full
・余った時間：min(remain, A)
→ 余った時間がA秒より短いなら、その分だけ走る。
→ もし余りがA秒以上なら、A秒分は確実に走っている。
5. 走った距離を求める → 1秒あたりSメートル × 総走行時間
S, A, B, X = map(int, input().split())
cycle = A + B
full = X // cycle
remain = X % cycle
distance = S * (A * full + min(remain, A))
print(distance)
B - Most Frequent Substrings
方針📝
Sから長さKの部分文字列を全部取り出し、それぞれの出現回数を数える。
その回数にあたる部分文字列をすべて集めて、辞書順で並べる。
from collections import Counter
N, K = map(int,input().split())
S = input().strip()
# Sから長さKの部分文字列をすべて取り出す
sub = [S[i:i+K] for i in range(N-K+1)]
c = Counter(sub)
x = max(c.values())
max_sub = sorted([t for t, c in c.items() if c == x])
print(x)
print(*max_sub)
PythonならばcollectionsのCounterを使うことで楽に出現回数の記録が可能。
C - Brackets Stack Query
クエリが順番に来て、
- 「
（」または「)」を追加する（1 c） - 末尾の１文字を削除する（
2）
という操作をして、操作をする度に今の文字列Sが良い括弧列になっているのかを判定する問題。
良い括弧列とは？
⭕️良い例
()(())(()())- 空文字列（何もない）
❌悪い例
-
)((最初に閉じている) -
(()(閉じ忘れ) -
)))(閉じすぎ）
方針📝
1. 文字列の末尾に「(」や「)」を追加・削除するたびに
現在のbalance（開きと閉じの差を更新
2. 今までの最小balance(min_balance)を記録。
これで「途中でマイナスになったかどうか」を判定。
3. 各クエリ後に
-
balance==0（開きと綴じが一致） -
min_balance > 0（途中で閉じすぎていない）
の２つを満たせば、「Yes」、そうでなければ「No」
入力から準備まで
-
mは現在の文字列をリストで表したもの -
balanceは「(を+1、「)」を−1した合計 -
min_balanceは今までのbalanceの最小値（途中で閉じすぎたかを見る） -
historyは各状態（balanceとmin_balance）を記録しておく履歴
Q = int(input())
m = []
balance = 0
min_balance = 0
history = [(0, 0)]
①追加クエリのとき(1 c)
◽️処理の流れ
- 文字
cをmに追加 - もし「
(」ならbalance += 1
もし「)」ならbalance -= 1 -
min_balanceを更新（途中でマイナスになったら記録） - 状態 (
balance,min_balance) を履歴(history)に保存
if query[0] == "1":
c = query[1]
m.append(c)
if c == "(":
balance += 1
else:
balance -= 1
min_balance = min(min_balance, balance)
history.append((balance, min_balance))
②追加クエリのとき(2)
◽️処理の流れ
- 文字列の末尾を削除
- 履歴(
history)からも削除 -
balanceとmin_balanceを、ひとつ前の状態に戻す
else:
m.pop()
history.pop()
balance, min_balance = history[-1]
③判定部分
- 開きと綴じの数が同じ
- 途中で閉じすぎていない
上記2点を確認
if balance == 0 and min_balance >= 0:
print("Yes")
else:
print("No")
提出コード
Q = int(input())
m = []
balance = 0
min_balance = 0
history = [(0, 0)]
for _ in range(Q):
query = list(input().split())
if query[0] == "1":
c = query[1]
m.append(c)
if c == "(":
balance += 1
else:
balance -= 1
min_balance = min(min_balance, balance)
m.append(c)
history.append((balance, min_balance))
else:
m.pop()
history.pop()
balance, min_balance = history[-1]
if balance == 0 and min_balance >= 0:
print("Yes")
else:
print("No")
E - Wind Cleaning
「木」というのはループのないグラフ（繋がっているけど閉じていない）のこと。木の頂点vをひとつ選んだ時に、頂点から一番遠い頂点の番号を求める問題。
方針📝
「木の直径」
木の中で最も遠い２つの点（距離が最大のペア）を直径という。
この直径の両端をp1,p2とした時にどの頂点vからも一番遠い頂点 は必ずp1かp2のどちらになるということを踏まえて問題を解いて行きます。
1. 1番遠い点p1を探す
2. p1から一番遠い点p2を探す（これで直径の両端を確定）
3. p1からの距離dist1とp2からの距離dist2をそれぞれ求める
4. 各頂点vについて
-
dist1[v]>dist2[v]→p1が遠い -
dist1[v]<dist2[v]→p2が遠い - 同じならば番号の大きい方
①グラフの作成
N = int(input())
g = [[] for _ in range(N + 1)]
for _ in range(N - 1):
a, b = map(int, input().split())
g[a].append(b)
g[b].append(a)
②BFS（幅優先探索）
BFSとは、「近い順に探索していく」方法。
ここでは、dist[i] に「startからiまでの距離」を記録します。
from collections import deque
def bfs(start):
dist = [-1] * (N + 1)
dist[start] = 0
q = deque([start])
while q:
v = q.popleft()
for nxt in g[v]:
if dist[nxt] == -1:
dist[nxt] = dist[v] + 1
q.append(nxt)
③一番遠い頂点を見つける
一番距離が遠い頂点をbest_iに保存
同じ距離なら、番号が大きい方を採用
best_i = 1
for i in range(2, N + 1):
if dist[i] > dist[best_i]:
best_i = i
elif dist[i] == dist[best_i] and i > best_i:
best_i = i
return best_i, dist
④BFSの実行と拡張点の答えを出力
- まず「1」から最も遠い点 →
p1 - つぎに p1 から最も遠い点 →
p2
→ これで木の「直径の両端」が確定！ -
p1からの距離とp2からの距離をdist1,dist2へ
各頂点vについて：
-
p1の方が遠ければ →p1 -
p2の方が遠ければ →p2 - 同じなら → 番号が大きい方
p1, _ = bfs(1)
p2, dist1 = bfs(p1)
_, dist2 = bfs(p2)
for v in range(1, N + 1):
if dist1[v] > dist2[v]:
print(p1)
elif dist1[v] < dist2[v]:
print(p2)
else:
print(max(p1, p2))
提出コード
import sys
from collections import deque
N = int(input())
g = [[] for _ in range(N + 1)]
for _ in range(N - 1):
a, b = map(int, input().split())
g[a].append(b)
g[b].append(a)
def bfs(start):
dist = [-1] * (N + 1)
dist[start] = 0
q = deque([start])
while q:
v = q.popleft()
for nxt in g[v]:
if dist[nxt] == -1:
dist[nxt] = dist[v] + 1
q.append(nxt)
best_i = 1
for i in range(2, N + 1):
if dist[i] > dist[best_i]:
best_i = i
elif dist[i] == dist[best_i] and i > best_i:
best_i = i
calc = best_i
return calc, dist
p1, _ = bfs(1)
p2, dist1 = bfs(p1)
_, dist2 = bfs(p2)
for v in range(1, N + 1):
if dist1[v] > dist2[v]:
print(p1)
elif dist1[v] < dist2[v]:
print(p2)
else:
print(max(p1, p2))
結果
ABCDE 5完
順位 1441st / 12157
パフォーマンス 1360
レーティング 1078 → 1113 (+35) Highest更新！
感想
今回はD問題を解くことができませんでした。（水色diffらしい）
難しい問題をうまく避けてE問題をしっかり通すことができ、Highestを更新できたことは良かったです。