今回はPythonでABC424をABCまで解くことができたので、その備忘録を纏めます。
コンテスト概要
AtCoder Beginner Contest 424
開催日:2025年9月20日 21:00-22:40
A - Isosceles
入力a,b,cが二等辺三角形であるかを判定する問題。
a, b, c = map(int,input().split())
if a==b or a==c or b==c:
print("Yes")
else:
print("No")
B - Perfect
N人の中でM問の問題全て解けた人の人数を解けた人の順番で出力する問題。
入力の形式が、『人Aが問題Bに正解した』という様に与えられる。
方針📝
解答状況を記録するリストとM問全て解答した人を格納するリストをそれぞれ用意。
入力に応じて適宜管理する。
N, M, K = map(int,input().split())
solved = [set() for _ in range(N+1)]
ended = set()
res = []
for _ in range(K):
A, B = map(int,input().split())
solved[A].add(B)
# 解答状況の人AがM問解けているならば、endedへ追加
if len(solved[A]) == M and A not in ended:
res.append(A)
ended.add(A)
print(*res)
C - New Skill Acquired
Aのスキルを獲得するにはBが必要で(A,B)=(0,0)の場合は習得済であり、
入力値から最終的に幾つのスキルを習得することができるかを出力する問題。
解いている際に、ゲーム開発したことがないけど、ゲーム内部のプログラムってこんな感じの構造になっているのかなとか思ったりしました。
方針📝
スキルの依存関係をグラフ構造に直し、最終的に何個習得できるかを数える。
1. 各スキルには($A_i$,$B_i$)という習得条件が与えられる
- (
0,0)の場合 → 最初から取得済 - それ以外の場合 → $A_i$または$B_i$のどちらかを習得済みなら解放
2. 「条件を満たしたら習得できる」という関係を有向グラフへ
例：スキル3の条件が($A_i$,$B_i$)なら『$A_i$を習得済なら3を習得可能』を有向グラフで表すと、$A_i→$ 3と表すことができる。
3. 有向グラフを作成した後に、BFS（幅優先探索) で習得スキルを数え上げる
- 初期取得済みスキル（条件が(
0,0)のもの）をキューに入れる - キューから取り出し、習得可能になるスキルを探索して追加する
- 全部処理したら、習得できたスキルの数を数える
入力値からBFS準備（有向グラフ作成）まで
from collections import deque
N = int(input()) # スキル数
adj = [[] for _ in range(N+1)] # 習得条件のグラフ（隣接リスト）
learned = [False] * (N+1) # 習得済みかどうかを管理
q = deque() # BFS用のキュー
for i in range(1, N+1):
a, b = map(int, input().split())
if a == 0 and b == 0:
learned[i] = True # 初期習得済みスキル
q.append(i) # BFSのスタート地点に追加
else:
if a != 0:
adj[a].append(i) # Aを習得したらiが習得可能
if b != 0:
adj[b].append(i) # Bを習得したらiが習得可能
-
adj[x]: スキルxを習得したときに習得可能なスキル一覧 -
learned[i]: スキル i が習得済みかどうかのフラグ -
q: BFSで処理中のスキルを管理するキュー - 入力を読みながら依存関係を構築
- (
0,0) の場合は、最初から習得済みとしてBFSの開始点に - そうでなければ、依存関係の辺を張ってグラフを作る
BFSのループ箇所
while q:
x = q.popleft() # 習得済みのスキルを取り出す
for y in adj[x]: # そこから習得可能になるスキルを調べる
if not learned[y]:
learned[y] = True # 新しく習得できたらマーク
q.append(y) # さらに探索するためキューに追加
- すでに習得済みのスキル
xを取り出し、そこから習得できるスキルyを確認 - 未習得なら新たに習得し、キューに追加して探索を広げる
C問題全体像
from collections import deque
N = int(input())
adj = [[] for _ in range(N+1)] # 習得条件のグラフ（隣接リスト）
learned = [False] * (N+1) # 習得済みかどうかを管理
q = deque() # BFS用のキュー
for i in range(1, N+1):
a, b = map(int, input().split())
if a == 0 and b == 0:
learned[i] = True # 初期習得済みスキル
q.append(i) # BFSのスタート地点に追加
else:
if a != 0:
adj[a].append(i) # Aを習得したらiが習得可能
if b != 0:
adj[b].append(i) # Bを習得したらiが習得可能
while q:
x = q.popleft() # 習得済みのスキルを取り出す
for y in adj[x]: # そこから習得可能になるスキルを調べる
if not learned[y]:
learned[y] = True # 新しく習得できたらマーク
q.append(y) # さらに探索するためキューに追加
print(sum(learned))
結果
ABC 3完
順位 3607th / 9795
パフォーマンス 774
レーティング 1083 → 1048 (-35)
感想
直近の成績かなり下降気味なので、めげずに少しずつ精進する時間を確保して、解けたという成功体験を徐々に積んでいきたいと思います。