[ABC404] ABC 404(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)

Posted at 2025-05-04

[ABC404] ABC 404(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)

A問題

set に S の文字を一つずつ登録する。
ord と chr を使ってアルファベットを数字から手に入れる。
in を使って存在判定をする。

A.py

"""
<方針>
- `set` に `S` の文字を一つずつ登録する。
- `ord` と `chr` を使ってアルファベットを数字から手に入れる。
- `in` を使って存在判定をする。
"""
# 入力
S = input()

# set
se = set()
for s in S:
  se.add(s)

# アルファベット生成
alphabets = []
for i in range(26):
  alphabet = chr(i + ord("a"))
  alphabets.append(alphabet)

# 存在判定
for alphabet in alphabets:
  # setになければ、
  if not (alphabet in se):
    # 出力
    print(alphabet)
    # プログラム終了
    exit()

B問題

先に回転する。
- 回転のパターンは 0 90 180 270 の 4 パターンのみ。
- 回転の方法は * と zip を使って行う。
回転させた後に、黒と白が異なるところを反転させる。

B.py

"""
<方針>
- 先に回転する。
  - 回転のパターンは `0 90 180 270` の `4` パターンのみ。
  - 回転の方法は `*` と `zip` を使って行う。
- 回転させた後に、黒と白が異なるところを反転させる。
"""
# 入力
N = int(input())
SS = [list(input()) for _ in range(N)]
TT = [list(input()) for _ in range(N)]

# 引数の違うところをカウントする関数
def count_diff(SS, TT):
  ans = 0
  for i in range(N):
    for j in range(N):
      if(SS[i][j] != TT[i][j]):
        ans += 1
  
  return ans


# 最適回数
ans = float("inf")
# 回転回数
for rot in range(4):
  # コピー
  new_SS = [S[:] for S in SS]
  # rot回、回転させる。
  for _ in range(rot):
    new_SS = list(zip(*reversed(new_SS)))
  
  # 回転させた分だけ操作カウント
  tmp = rot
  
  # 違うところをカウント
  tmp += count_diff(new_SS, TT)
  
  # 最適回数を更新
  ans = min(ans, tmp)

# 出力
print(ans)

C問題

方針

N == M であることをまず確かめる。
それぞれの頂点を訪れたかどうかを探索で確認していき、訪れた頂点に達したら終了する。
全ての頂点を訪れており、最後に訪れた頂点が最初の頂点ならば、サイクルグラフ

前提

C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう．
AとB問題では，基本的に制約条件を見ずにやっても解ける．
しかし，C問題以降では，制約条件を見ないと必ずTLEすると思っても良い．
詳しい話は私の352回の記事のC問題の解説に記したので，是非参照してほしい．

C.py

"""
<方針>
- `N == M` であることをまず確かめる。
- それぞれの頂点を訪れたかどうかを探索で確認していき、訪れた頂点に達したら終了する。
- 全ての頂点を訪れており、最後に訪れた頂点が最初の頂点ならば、サイクルグラフ
"""
# 入力
N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
  A, B = map(int, input().split())
  A -= 1
  B -= 1
  
  E[A].append(B)
  E[B].append(A)
  

# 頂点と辺の数が合致するかどうかを確認する。
if(N != M):
  print("No")
  exit()

# 訪れたかどうか
visited = [False]*N

# キューに[前回訪れた頂点、今訪れている頂点]を入れる。
q = [[-1, 0]]

# DFS
while q:
  t, u = q.pop()
  
  # 訪れていれば終了する。
  if(visited[u]):
    break
  
  # 訪れチェック
  visited[u] = True
  
  # 次の頂点を訪れる。
  for v in E[u]:
    # 前回の頂点は入れない。
    if(t != v):
      # 次の頂点を追加する。
      q.append([u, v])
  
# 全て訪れていれば
if(all(visited)):
  print("Yes")
else:
  print("No")

D問題

それぞれの動物園へ行くか行かないかの bit 探索を、0 回行く、 1 回行く、 2 回行くの 3 進数探索をすれば良い。

D.py

"""
<方針>
- それぞれの動物園へ行くか行かないかの `bit` 探索を、`0` 回行く、 `1` 回行く、 `2` 回行くの `3` 進数探索をすれば良い。
"""
# 入力を受け取る
N, M = map(int, input().split())
C = list(map(int, input().split()))
BB = [[] for _ in range(N)] # AAのindexを変えたもの。BB[動物園][動物]
for i in range(M):
  K, *A = map(int, input().split())
  for a in A:
    a -= 1
    BB[a].append(i)

# 3進数探索
ans = float("inf")
for i in range(3**N):
  # 動物を何回見たかどうか
  animals = [0]*M
  
  # かかったお金
  tmp = 0
  
  # それぞれの動物園を何回訪れたか
  for j in range(N):
    # moがj番目の動物園を訪れた回数
    i, mo = divmod(i, 3)
    # 訪れた動物園で見た動物の回数を登録する。
    for b in BB[j]:
      animals[b] += mo
    # 動物園に貢献した分を登録
    tmp += mo*C[j]
  
  # 全ての動物を2回以上見ていれば、
  if(all([a>=2 for a in animals])):
    ans = min(ans, tmp)

print(ans)

補足

関係するリンク(参考文献など)

今回のコンテスト

筆者について

その他

間違いを含んでいる可能性があります．
方針と言いつつ，方針ではない感想などを書いている可能性があります．
A問題から解説がだんだん省略されます．
コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．

最後に一言

可愛い後輩の力を借りて早起きに挑戦します。
確かピクミン3では地球っぽい星のことを PNF-404 って呼んでた気がします。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up