今回はPythonでABC427をABCDEまで解くことができたので、その備忘録を纏めます。
コンテスト概要
AtCoder Beginner Contest 427
開催日:2025年10月11日 21:00-22:40
A - ABC -> AC
長さが奇数の文字列Sが与えられるので、中央の文字を削除して得られる文字列を算出する問題。
S = input()
mid = len(S) // 2
print(S[:mid] + S[mid+1:])
B - Sum of Digits Sequence
数列$A=(A_0,A_1,A_2,...)$が
\begin{align}
A_0&=1 \\
A_{i}&=\sum^{t-1}_{j=0}f(A_{j}) (i\geq1)
\end{align}
ただし
f(x)=(xの各桁の和)
与えられたNに対して$A_{N}$を求める問題。
方針📝
1. 桁和関数 f(x) の定義
文字列化して各桁を整数に変換し、sum() で合計する：
def f(x):
return sum(int(d) for d in str(x))
これで f(123) = 6 のように計算可能。
2. 再帰的定義をそのまま実装
A(i) = sum(f(A(j)) for j in range(i))
3.メモ化による効率化 (@lru_cache)
$A_{i}$の計算では$A_{0}$から $A_{i-1}$ まで何度も再帰的に呼ばれる。
計算結果をキャッシュして再利用することで、重複計算を防ぐ。
from functools import lru_cache
@lru_cache(maxsize=None)
def A(n):
if n == 0:
return 1
return sum(f(A(j)) for j in range(n))
提出コード
from functools import lru_cache
def f(x):
return sum(int(d) for d in str(x))
# メモ化
@lru_cache(maxsize=None)
def A(n):
if n == 0:
return 1
return sum(f(A(j)) for j in range(n))
N = int(input())
print(A(N))
@lru_cache(maxsize=None)についての参考記事
記憶が正しければ、競技プログラミングの鉄則にも載っていた気がする。
C - Bipartize
頂点N、辺がMの単純無向グラフが与えられ、二部グラフにするためには、最低何回辺を削除する必要があるかを求める問題。
方針📝
二部グラフとは...
点を２つのグループに分けて
同じグループの中では辺（線） がつながっていない状態。
例えば
頂点をAグループとBグループに分ける方法を全て試す。（本文では白黒）
点が３つある場合なら：AAB/ABA/ABB/BAA/BAB/BBA
など全部で$2^{3}=8$通りの分け方がある。
各分け方で
- 辺が「AとBの間」にあるなら残せる
- 辺が「同じグループ同士」なら削除
全部の分け方を調べて残せる線の数が一番多い分け方を全探索する。その時の削除する辺の最小数は『全体の辺の数-残せる辺の最大数』となる。
1. index-1でグラフの読み込み
N, M = map(int, input().split()) # 点と線の数
edges = []
for _ in range(M): # 線の情報を読み取る
u, v = map(int, input().split())
edges.append((u-1, v-1))
これで「どの点とどの点がつながっているか」を edges に格納。
（-1 は、プログラムで0番から数えるため）
2. bit全探索
maskという数字を使って、点をA/Bに分ける（ビットと呼ばれる0,1パターンを使って点ごとにAならば0、Bならば1とする。）
best = 0
for mask in range(1 << N):
3. 辺の確認
((mask >> u) & 1) は「点がどちらのグループか」を確認。
もし2つの点が違うグループにいたら、辺は残せるので cnt += 1
cnt = 0
for u, v in edges:
if ((mask >> u) & 1) != ((mask >> v) & 1):
cnt += 1
提出コード
N, M = map(int, input().split())
edges = []
for _ in range(M):
u, v = map(int, input().split())
edges.append((u-1, v-1))
best = 0
for mask in range(1 << N):
cnt = 0
for u, v in edges:
if ((mask >> u) & 1) != ((mask >> v) & 1):
cnt += 1
if cnt > best:
best = cnt
print(M-best)
bit全探索についての参考記事
二部グラフについての参考記事
うさぎでもわかる離散数学（グラフ理論） 第9羽 グラフの基礎3
アルゴリズムと数学 演習問題集
D - The Simple Game
N頂点M辺の有向グラフがあり、各頂点にはAとBの文字が書かれている。
初めは頂点１に駒があり、AliceとVovが順番に動かす。
（それぞれKなので合計で2K回動かす)
最後に駒が止まっている頂点vの文字がAならAlice、BならばBobが勝つ。
方針📝
考え方
「今コマが頂点uにいて、あとt回動くとき、Aliceが勝てるか」
これを全部の頂点と残り回数tについて計算しておけば、最初（頂点1,残り2K回）でAliceが勝てるかどうかが分かる。
これをdp[u][t]という表に入れておく。
dp[u][t]=Trueならば、「その状態からAliceが勝てる」
dp[u][t]=Falseならば、「その状態からAliceが勝てない（Bobが勝つ）」
dpの作成方法
1.動く回数が0(t=0)の時
もう動かないので勝敗は頂点uの文字で決まる。
-
S[u]=='A'ならdp[u][0]=True(Aliceの勝ち) -
S[u]=='B'ならdp[u][0]=False(Bobの勝ち)
入力部分とdpの初期部分の作成
T = int(input())
for _ in range(T):
N, M, K = map(int,input().split())
S = input().strip()
adj = [[] for _ in range(N)]
for _ in range(M):
u, v = map(int, input().split())
adj[u-1].append(v-1)
dp = [[False] * (2*K+1) for _ in range(N)]
# t＝0部分の勝敗を表へ
for i in range(N):
dp[i][0] = (S[i] == "A")
2.動く回数がt>0の時
2-1 tが偶数の場合（次に動くのはAlice）
Aliceは自分が勝てるように「行き先v（隣の頂点）」を選ぶ。
→ Aliceが勝てる条件は「行き先のうち１つでもdp[v][t-1]がTrue」
つまりdp[u][t] = any(dp[v][t-1] for v in neighbors)
2-2 tが奇数の場合（次に動くのはBob）
BobはAliceに負けさせようとするので、
Aliceが確実に勝つにはBobがどの行き先を選んでも負ける状態。
→ Aliceが勝てる条件は「すべての行き先vでdp[v][t-1]がTrue」
つまりdp[u][t] = all(dp[v][t-1] for v in neighbors)
for t in range(1, 2*K+1):
# 2-1:偶数の場合
if t % 2 == 0:
for u in range(N):
# 行き先のうち１つでもdp[v][t-1]がTrueならばdp[u][t]をTrue
dp[u][t] = any(dp[v][t-1] for v in adj[u])
# 2-2:奇数の場合
else:
for u in range(N):
# すべての行き先でdp[v][t-1]がTrueならばdp[u][t]をTrue
dp[u][t] = all(dp[v][t-1] for v in adj[u])
提出コード
T = int(input())
for _ in range(T):
N, M, K = map(int,input().split())
S = input().strip()
adj = [[] for _ in range(N)]
for _ in range(M):
u, v = map(int, input().split())
adj[u-1].append(v-1)
dp = [[False] * (2*K+1) for _ in range(N)]
for i in range(N):
dp[i][0] = (S[i] == "A")
for t in range(1, 2*K+1):
if t % 2 == 0:
for u in range(N):
dp[u][t] = any(dp[v][t-1] for v in adj[u])
else:
for u in range(N):
dp[u][t] = all(dp[v][t-1] for v in adj[u])
if dp[0][2*K]:
print("Alice")
else:
print("Bob")
E - Wind Cleaning
方針📝
1. 「今の状態」を記録
どのマスにどのゴミがあるのか「ビットマスク」で表す。
例えば、12×12マスならば、さだい144個のマスがある。
各マスを「1」か「0」で記録
-
1→ ゴミがある -
0→ ゴミがない
0,1で表すことで例えば下記のように表すことができ、
マス番号：0 1 2 3 4 ...
状態 ：1 0 1 0 0 ...
「今どこにゴミがあるのか」がたった1つの数字（ビット列）で表すことができる。
2. BFS（幅優先探索）
BFSで「すべての動きを少しずつ試して、一番早くゴミがなくあるルートを見つける」
3.次の状態を作成する
- 今のゴミの位置を全部1つずつ動かし、外に出たら消す
- 高橋くんのますに動いたら「汚れる」のでその方向はスキップする
4.同じ状態は調べない
すでに試したゴミの配置は無限ループにならないように「visited（訪問済み）」として記録する
コードの流れ
① 入力と準備
グリッドを読み込み、「T」と「＃」がある場所を探して記録。
H, W = map(int, input().split())
S = [list(input().strip()) for _ in range(H)]
tx, ty = -1, -1 # 高橋くんの位置
mask = 0 # ゴミのビットマスク
for i in range(H):
for j in range(W):
if S[i][j] == "T": tx, ty = i, j
elif S[i][j] == "#": mask |= 1 << pos(i, j)
② BFSの開始
queue = deque([(mask, 0)])
visited = set()
visited.add(mask)
dirs = [(-1,0),(1,0),(0,-1),(0,1)]
ans = -1
while queue:
state, step = queue.popleft()
if state == 0:
ans = step
break
③ ゴミを動かす
4方向（上下左右）に動かす。
「safe」がTrueなら汚れずに動かせたので、次の状態をキューに追加。
dirs = [(-1,0),(1,0),(0,-1),(0,1)]
for dx, dy in dirs:
new_mask = 0
safe = True
for b in bits:
x, y = divmod(b, W)
nx, ny = x + dx, y + dy
# 外に出たら消える
if not (0 <= nx < H and 0 <= ny < W): continue
# 高橋くんにぶつかったらアウト
if (nx, ny) == (tx, ty):
safe = False
break
new_mask |= 1 << pos(nx, ny)
提出コード
from collections import deque
H, W = map(int, input().split())
S = [list(input().strip()) for _ in range(H)]
def pos(i,j):
return i*W + j
tx = ty = -1
mask = 0
for i in range(H):
for j in range(W):
if S[i][j] == "T":
tx, ty = i, j
elif S[i][j] == "#":
mask |= 1 << pos(i,j)
queue = deque([(mask, 0)])
visited = set()
visited.add(mask)
dirs = [(-1,0),(1,0),(0,-1),(0,1)]
ans = -1
while queue:
state, step = queue.popleft()
if state == 0:
ans = step
break
bits = [i for i in range(H*W) if (state >> i) & 1]
for dx, dy in dirs:
new_mask = 0
safe = True
for b in bits:
x, y = divmod(b, W)
nx, ny = x + dx, y + dy
if not (0 <= nx < H and 0 <= ny < W):
continue
if (nx, ny) == (tx, ty):
safe = False
break
new_mask |= 1 << pos(nx, ny)
if not safe:
continue
if new_mask not in visited:
visited.add(new_mask)
queue.append((new_mask, step + 1))
print(ans)
結果
ABCDE 5完
順位 950th / 11200
パフォーマンス 1533
レーティング 1004 → 1078 (+74)
感想
今回はABCDEまで解くことができ、久しぶりに水色パフォーマンスでした。今回の内容をしっかり復讐しつつ、次回もEまで解けるように精進していきたいです。