今回はPythonでABC412をABDを解くことができたので、備忘録を纏めました。
コンテスト概要
日本最強プログラマー学生選手権～Advance～ -予選- （AtCoder Beginner Contest 412）
開催日:2025年6月28日 21:00-22:40
A - Task Failed Successfully
方針
N日間の間の中でAとBを比べてBの方が大きかった場合をカウントするだけの問題。
N = int(input())
ans = 0
for i in range(N):
a, b = map(int,input().split())
if a < b:
ans += 1
print(ans)
B - Precondition
方針
文字列Sにおいて、先頭以外の位置（2文字目以降）にある英大文字について、
その直前の文字（S[i - 1]）が 文字列Tに含まれていない場合は不適。
S[i] が英大文字かどうかを isupper() で判定。
かつ、直前の文字S[i - 1]がTに含まれていなければ、Noと返す。
S = input().strip()
T = input().strip()
ok = True
for i in range(1, len(S)):
if S[i].isupper() and S[i - 1] not in T:
ok = False
break
print("Yes" if ok else "No")
D - Make 2-Regular Graph
| 項目 | 内容 |
|---|---|
| 目標 | 全ての頂点の次数が2のグラフにするための最小操作数を求める |
| 方法 | 全てのN本の辺の組み合わせから「次数2」のものを列挙し、差分をとって操作数を最小化 |
| ポイント | グラフ構造、次数チェック、全探索、集合演算 |
方針
- 頂点数Nが最大8までなので、「すべての可能なグラフ構造を試す」（＝全探索）が可能
- 重要なのは、「N個の辺でできた、すべての頂点の次数が2のグラフ（＝サイクル構成）」だけを調べること
- その中で、現在のグラフとどれくらい違うか（追加や削除が必要か）を調べて最小回数を更新
サイクルグラフかどうかの判定
頂点の次数を数えて、すべて2かをチェック
- 与えられた辺集合 edge_set に対して、各頂点に何本の辺がつながっているか（=次数）を数える
- すべての頂点の次数が 2本ちょうど ならば OK（=理想の状態）
def is_valid_cycle_graph(edge_set):
degree = [0] * N
for a, b in edge_set:
degree[a] += 1
degree[b] += 1
return all(d == 2 for d in degree)
全ての可能な辺の組み合わせを試す
-
0 〜 N − 1のすべての可能な辺を列挙 -
(i, j)としてi < jを守ることで、無向グラフの重複を防ぐ
all_possible_edges = [(i, j) for i in range(N) for j in range(i + 1, N)]
全てのN本の辺の組み合わせを試す
- combinations(all_possible_edges, N) は、N本の辺を選ぶすべての組み合わせ
- 「次数が2のグラフ」は必ず辺の本数がN本になる
min_ops = float('inf') # 最小操作回数を無限大で初期化
for edge_subset in combinations(all_possible_edges, N):
差分のコスト計算
to_add = edge_set - edges
to_remove = edges - edge_set
ops = len(to_add) + len(to_remove)
現在の候補 edge_set を実現するには：
- edges にない辺：追加
- edge_set にない現在の辺：削除
最後に最小値の更新を行う。
全体
from itertools import combinations
import sys
input = sys.stdin.read
data = input().split()
N = int(data[0])
M = int(data[1])
edges = set()
for i in range(M):
a = int(data[2 + 2 * i]) - 1
b = int(data[3 + 2 * i]) - 1
edges.add((min(a, b), max(a, b)))
from itertools import permutations
def is_valid_cycle_graph(edge_set):
degree = [0] * N
for a, b in edge_set:
degree[a] += 1
degree[b] += 1
return all(d == 2 for d in degree)
all_possible_edges = [(i, j) for i in range(N) for j in range(i + 1, N)]
min_ops = float('inf')
# 全ての辺集合の中から、サイズがNのサブセット（次数2で全頂点カバーする可能性がある）を列挙
for edge_subset in combinations(all_possible_edges, N):
edge_set = set(edge_subset)
if is_valid_cycle_graph(edge_set):
# 差分を計算（追加 + 削除の最小コスト）
to_add = edge_set - edges
to_remove = edges - edge_set
ops = len(to_add) + len(to_remove)
min_ops = min(min_ops, ops)
print(min_ops)
結果
ABD 3完
順位 2273th / 11564
パフォーマンス 1144
レーティング 238 → 473 (+235)
感想
今回のコンテストで運よく入茶することができました。
D問題に関しては、制約が緩かったため解けたのでラッキーでした。