今回はPythonでABC420をABCDEGまで解くことができたので、その備忘録を纏めます。
コンテスト概要
AtCoder Beginner Contest 420
開催日:2025年8月24日 21:00-22:40
A - What month is it?
X, Y = map(int, input().split())
print((X + Y - 1) % 12 + 1)
B - Most Minority
方針📝
- スコア管理用のリストの準備
- 投票を1回ずつ処理するループを作成
- ループ内で各回の集計と得点の加算
- 全投票終了後の結果を求める
# 人数Nと投票回数Mを入力
N, M = map(int,input().split())
# N人分の投票内容（文字列）をリストSに格納
S = [input().strip() for _ in range(N)]
# N人分のスコアを0で初期化
score = [0] * N
# jを0からM-1までループ（jは投票の回数を表す）
for j in range(M):
# j回目の投票内容をリストvotesに集める
votes = [S[i][j] for i in range(N)]
# j回目の投票での"0"と"1"の票数を数える
x = votes.count("0")
y = votes.count("1")
# ケース1: 全員が同じ選択をした場合
if x == 0 or y == 0:
for i in range(N):
score[i] += 1
# ケース2: "0"が少数派だった場合
elif x < y:
for i in range(N):
if votes[i] == "0":
score[i] += 1
# ケース3: "1"が少数派だった場合
else:
for i in range(N):
if votes[i] == "1":
score[i] += 1
# 計算されたスコアの中から最高得点を求める
max_score = max(score)
# スコアが最高得点と一致する人の番号(i+1)をリストに集める
ans = [str(i+1) for i in range(N) if score[i] == max_score]
# リストの要素をスペースで連結して出力
print(" ".join(ans))
C - Sum of Min Query
この問題は、大量のクエリを効率的に処理する必要があるため、計算量をいかに削減するかが鍵となります。
方針📝
制約を見る限りNとQが最大で$2×10^{5}$なので、forループをN回まわしてmin(A[k],B[k])の合計を計算すると、全体の計算量が$O(NQ)$となりTLEになります。
そこでクエリを処理する前に合計値を最初に計算しておくことで、クエリごとの差分だけを更新するように実装をしました。
クエリ後に差分だけを更新
各クエリでは、A[x]またはB[x]が変更される。そこで、以下の手順で合計値Sを更新する。
1.古い値の影響を取り除く：合計値Sから、更新前のmin(A[x],B[x])の値を引き算
2.配列の値を更新：A[x]またはB[x]を新しい値vに変更
3.新しい値の影響を加える：合計値Sに、更新後のmin(A[x],B[x])の値を加える
最後に更新後の合計値を出力します。
この方針により、各クエリの処理は配列の更新と数回の加減算のみとなり、計算量は$O(1)$で済みます。全体の計算量は、最初の合計値の計算$O(N)$とQ回のクエリ処理$O(Q)$を合わせて$O(N+Q)$となります。
import sys
input = sys.stdin.readline
N, Q = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
# 最初に合計値を計算
S = sum(min(A[i], B[i]) for i in range(N))
for _ in range(Q):
c, x, v = input().split()
x = int(x) - 1
v = int(v)
# ステップ 1: 古い値の影響を取り除く
S -= min(A[x], B[x])
# ステップ 2: 配列の値を更新する
if c == "A":
A[x] = v
else:
B[x] = v
# ステップ 3: 新しい値の影響を加える
S += min(A[x], B[x])
# 更新後の合計値を出力する
print(S)
D - Toggle Maze
この問題は、グリッド状の最短経路問題なので幅優先探索（BFS） が有効そうに見えますが、通常のBFSとは異なり、「スイッチを踏むとドアの状態が全体で変わる」という厄介な要素があります。
着眼点
単純な位置だけでは状態を管理できない
通常のBFSの問題ならば、今いるマス(i, j)だけで状態を表現しますが、この問題では同じマス(i, j)にいても、「ドアが初期状態」「ドアが反転している状態」で、進めるマスが変わります。
「状態の拡張」
現在地だけでなくドアの状態もまとめて1つの「状態」として考える必要があるため、状態を（現在の行,現在の列,ドアの状態）の３つの状態で管理します。（0と1で状態を管理）
方針📝
1. 状態管理用の３次元配列の準備
核状態への最小コストを記録するため、dist[i][j][w]という３次元配列を用意。dist[i][j][w]は「ドアの状態がwの時マス(i, j)に到達するための最小回数」を意味します。最初は全てをINFで初期化しています。
2. BFSのキューを準備
探索のためのキューを用意。スタートマス(si, sj)に、ドアの初期状態0で、コスト0に到達できるので、dist[i][j][0]=0として、キューに(si, sj, 0)を追加。
3. BFSの実行
キューから状態(i, j, w)を取り出し、そのマスカラ上下左右の近隣マス(ni, nj)へ移動できるかを試行。
-
通常判定
近隣マス(ni, nj)が障害物や、現在のドアの状態wで通れないデアではないかをチェック -
次の状態を計算
移動先のマス(ni, nj)がスイッチ?マスであれば、次のドアの状態nwは1 - w（０ → 1, 1 → 0）とし、そうでなければ、nw = w（状態変化なし） -
更新とキューへの追加
新しい状態(ni, nj, nw)へ現在のコストdより1大きいコストd+1で到達するのが、今までの記録dist[ni][nj][nw]よりも早い場合は、distを更新し、新しい状態をキューに追加。
4. ゴール判定
キューから取り出した状態の位置 (i, j) がゴールマス (gi, gj) であれば、その時点でのコストが答え。探索が終了してもゴールに到達できなければ、到達不可能と判断します。
from collections import deque
H, W = map(int, input().split())
grid = [list(input().strip()) for _ in range(H)]
# スタートとゴールの座標を探す
for i in range(H):
for j in range(W):
if grid[i][j] == "S":
si, sj = i, j
if grid[i][j] == "G":
gi, gj = i, j
INF = 10**9
# dist[行][列][ドアの状態] を INF で初期化
dist = [[[INF]*2 for _ in range(W)] for __ in range(H)]
# スタート地点の初期状態を設定
dist[si][sj][0] = 0
q = deque()
q.append((si, sj, 0))
# 上下左右の移動方向をまとめたリスト
dirs = [(1,0), (-1,0), (0,1), (0,-1)]
def ok_pass(ch, open_flag):
if ch == "#":
return False
if ch in [".", "S", "G", "?"]:
return True
if ch == "o":
return open_flag == 0 # ドア状態が0なら通れる
if ch == "x":
return open_flag == 1 # ドア状態が1なら通れる
return False
while q:
i, j, w = q.popleft()
d = dist[i][j][w]
# ゴールに到達したら、その時点のコストを出力して終了
if (i, j) == (gi, gj):
print(d)
exit()
# 上下左右の隣接マスを調べる
for di, dj in dirs:
ni, nj = i+di, j+dj
# グリッドの範囲内かチェック
if 0 <= ni < H and 0 <= nj < W:
cell = grid[ni][nj]
# 現在のドア状態で通行可能かチェック
if not ok_pass(cell, w):
continue
# 移動後のドア状態を計算
nw = w
if cell == "?":
nw = 1 - w # スイッチなら反転
# もし新しい状態へのより短い経路を見つけたら更新
if dist[ni][nj][nw] > d+1:
dist[ni][nj][nw] = d+1
q.append((ni, nj, nw))
# キューが空になってもゴールに到達しなかった場合
print(-1)
E - Reachability Query
この問題は、グラフの連結成分を動的に管理しつつ、各成分に関する情報を得ることが求められます。
着眼点👀
1. 連結成分の管理
タイプ3のクエリ「頂点vから黒色の頂点に到達できるか？」は、言い換えると「頂点vが属する連結成分内に、黒色の頂点が１つ以上存在するか？」ということ。グラフのへんは追加される一方なので、連結成分は時間ともに合体していきます。
2. 実行時間
タイプ3のクエリを処理する際に、頂点vからDFSやBFSで探索して黒い頂点を探す方法では、クエリの回数Qと頂点数Nが大きため、TLEになる。
3. Union-Find
頂点同士の連結関係を管理し、２つのグループを高速に操作するには、Union-Findを活用。辺の追加はuniteに対応。
4. Union-Findの拡張
通常のUnion-Findは、どの頂点が同じグループに属するかしか管理できません。今回は「そのグループに黒い頂点があるか」という管理が必要。そこで、Union-Findを拡張し、各連結成分の根（root）に、その成分が何この黒い頂点を含んでいるかを実装。
方針📝
着眼点より、黒い頂点の個数を管理する機能を追加したUinon-FIndを用いて、各クエリを高速に処理する。
1. データ構造の準備
-
UnionFIndクラスを作成。各連結成分の根に、その成分内の黒い頂点の数を記録するblack_count配列を追加 - 各頂点が現在黒いかどうかを個別に管理するため、
is_blackでブール型の配列を用意
2. クエリごとの処理
- タイプ1（辺の追加
u, v）
uf.unite(u, v)を呼び出すことで、unite処理の中で、２つの連結成分を合併する際に、それぞれのblack_countを合算して新しい根を記録 - タイプ2（色の反転
v）
is_black[v]を反転させ、-
vが白→黒になるとき：vが属する連結成分のblack_countを+1 -
vが黒→白になるとき：vが属する連結成分のblack_countを-1
-
- タイプ3（到達判定
v）
vが属する連結成分の根を見つけ、その根に記録されているblack_countが0より大きければYes、0ならばNoとなります。
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
# 各連結成分の根が、その成分内の黒頂点の数を管理する
self.black_count = [0] * n
# find: 頂点xの根を見つける（経路圧縮付き）
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
# unite: 頂点xとyの属する成分を併合する
def unite(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
# union by size: サイズの大きい方に小さい方を併合
if self.size[x] < self.size[y]:
x, y = y, x
self.parent[y] = x
self.size[x] += self.size[y]
# 黒頂点の数も合算する
self.black_count[x] += self.black_count[y]
# add_black: 頂点xの成分の黒頂点数を更新
def add_black(self, x, val):
r = self.find(x)
self.black_count[r] += val
# has_black: 頂点xの成分に黒頂点が存在するか判定
def has_black(self, x):
return self.black_count[self.find(x)] > 0
N, Q = map(int, input().split())
uf = UnionFind(N)
is_black = [False] * N # 各頂点の現在の色を管理
ans = []
for _ in range(Q):
query = input().split()
t = int(query[0])
# タイプ1: 辺の追加
if t == 1:
u, v = int(query[1]) - 1, int(query[2]) - 1
uf.unite(u, v)
# タイプ2: 色のトグル
elif t == 2:
v = int(query[1]) - 1
if is_black[v]: # 黒 -> 白
is_black[v] = False
uf.add_black(v, -1)
else: # 白 -> 黒
is_black[v] = True
uf.add_black(v, +1)
# タイプ3: 到達判定
else:
v = int(query[1]) - 1
if uf.has_black(v):
ans.append("Yes")
else:
ans.append("No")
print("\n".join(ans)))
G - sqrt(n²+n+X)
この問題は、数式をうまく変形することで、探索範囲を有限にできる問題です。
着眼点 👀
求める条件は
n^2+n+X が平方数(=m^2)
ということなので、
m^2 - n^2 - n = X
を満たす整数ペア$(m, n)$が存在する$n$を全て求めれば良い。
m^2 = n^2 + n + X
平方完成
m^2 + \frac{1}{4}=\left(n+\frac{1}{2} \right)^{2}+X
4m^2 + 1 = (2n+1)^2+4X
(2m)^2 - (2n+1)^2 = 4X - 1
因数分解
(2m-(2n+1))*(2m+(2n+1))=4X-1
a=2m-(2n+1),b=2m+(2n+1)
a*b=4X-1
2m=\frac{a+b}{2},2n+1=\frac{b-a}{2}
2m=\frac{a+b}{2},2n+1=\frac{b-a}{2}
n=\frac{b-a-2}{4}
条件整理
- $a,b$は$4X-1$の因数ペア
- $(a+b)/2$は偶数($m$が整数になる条件)
- $(b-a)/2$は奇数($2n+1$が奇数でなければならない)
方針📝
1. $D=4X-1$を計算
2. $D$の全ての約数ペア$(a, b)$を求める($a*b=D$)
3. 各ペアに対し
- $(a+b)$が4で割り切れる
- $(b-a)$が2で割り切れるならば$n=(b-a-2)/4$を候補へ
4. 全ての解$n$を昇順に出力
import sys
import math
X = int(input())
D = 4*X - 1
n_set = set()
for d in range(1, int(abs(D)**0.5) + 1):
if D % d != 0:
continue
for a in (d, -d):
b = D // a
if (a+b) % 4 == 0 and (b-a) % 2 == 0:
n = (b - a - 2) // 4
n_set.add(n)
n_list = sorted(n_set)
print(len(n_list))
print(*n_list)
結果
ABCDEG 5完
順位 569th / 11698
パフォーマンス 1713
レーティング 919 → 1061 (+142)
感想
今回は知っていたBFSやUnion-Findをコンテスト中にしっかり活用して解けたのが嬉しかったです。年内に水色目指して今後も取り組んでいこうと思います。