AtCoder Beginner Contest 404（Promotion for Engineer Guild）の解説記事です。
ABC404 A – Not Found
問題
問題文の要約は以下の通りです。
問題の要約
英小文字からなる長さ \(1\) 以上 \(25\) 以下の文字列 \(S\) に含まれない英小文字をひとつ出力せよ。
解説１
英小文字の一覧を用意して、1文字ずつ \(S\) に含まれているかどうか判定する。
解説
入力を受け取ります。
# 入力
S=input()英小文字の一覧を用意して、1文字ずつ \(S\) に含まれているかどうか判定します。英小文字の一覧は'abcdefghijklmnopqrstuvwxyz'で用意できます。
# S に含まれないアルファベットを出力
for s in 'abcdefghijklmnopqrstuvwxyz':
if s not in S:
print(s)
exit()解答
# 入力
S=input()
# S に含まれないアルファベットを出力
for s in 'abcdefghijklmnopqrstuvwxyz':
if s not in S:
print(s)
exit()解説２
英小文字の一覧はstring.ascii_lowercaseで用意されているのでこれを使用する。
string.ascii_lowercaseをそのままprintすると英小文字の一覧が出力されます。
import string
print(string.ascii_uppercase)abcdefghijklmnopqrstuvwxyz解説
stringを使用するのでこれをimportし、入力を受け取ります。
import string入力を受け取ります。
# 入力
S=input()英小文字の一覧を用意して、1文字ずつ \(S\) に含まれているかどうか判定します。英小文字の一覧はstring.ascii_lowercaseで用意できます。
# S に含まれないアルファベットを出力
for s in string.ascii_lowercase:
if s not in S:
print(s)
exit()解答
import string
# 入力
S=input()
# S に含まれないアルファベットを出力
for s in string.ascii_lowercase:
if s not in S:
print(s)
exit()ABC404 B – Grid Rotation
問題
問題文の要約は以下の通りです。
問題の要約
\(N\) 行 \(N\) 列からなるグリッド \(S\), \(T\) があります。以下の２つの操作を操作を好きな順序で好きな回数行うとき、グリッド \(S\) をグリッド \(T\) と一致させるために必要な操作回数の最小値を求めよ。
- グリッド \(S\) のマスを \(1\),つ選び、色を変更する。
- グリッド \(S\) 全体を \(90\) 度右に回転する。
解説
グリッド全体を回転する操作を最初に行い、\(S\), \(T\) で異なる色のマスが何マスあるか求める。
解説
入力を受け取ります。
# 入力
N=int(input())
S=[list(input()) for _ in range(N)]
T=[list(input()) for _ in range(N)]\(S\) を \(90\) 度右に回転する関数を定義します。
\( S=[[S_{1,1}S_{1,2} \cdots S_{1,N}], \cdots, [S_{N,1}S_{N,2} \cdots S_{N,N}]]\) を右回転させると、\( S=[[S_{N,1}S_{N-1,1} \cdots S_{1,1}], \cdots, [S_{N,N}S_{N-1,N} \cdots S_{1,N}]]\)なので S=[[S[N-j-1][i] for j in range(N)] for i in range(N)]と書くことができます。
# S を 90 度右に回転
def rotate(S):
S=[[S[N-j-1][i] for j in range(N)] for i in range(N)]
return S操作の最小回数をans=100**2とします。これは全マスの色を変更することで必ず一致させることができるためです。
# 操作の最小回数
ans=100**2操作の最小回数を求めます。まず、グリッド全体を回転する操作を最初に行い、\(S\), \(T\) で異なる色のマスが何マスあるか求めます。最後に答えを出力します。
# 回転の回数
for dif in range(4):
# i,j のマスを順に比較
for i in range(N):
for j in range(N):
if S[i][j]!=T[i][j]:
dif+=1
# 最小回数を更新
ans=min(ans,dif)
# 回転
S=rotate(S)
# 出力
print(ans)解答
# 入力
N=int(input())
S=[list(input()) for _ in range(N)]
T=[list(input()) for _ in range(N)]
# S を 90 度右に回転
def rotate(S):
S=[[S[N-j-1][i] for j in range(N)] for i in range(N)]
return S
# 操作の最小回数
ans=100**2
# 回転の回数
for dif in range(4):
# i,j のマスを順に比較
for i in range(N):
for j in range(N):
if S[i][j]!=T[i][j]:
dif+=1
# 最小回数を更新
ans=min(ans,dif)
# 回転
S=rotate(S)
# 出力
print(ans)ABC404 C – Cycle Graph?
問題
問題文の要約は以下の通りです。
問題の要約
\(N\) 頂点 \(M\) 辺の単純無向グラフが与えられるので、このグラフがサイクルグラフであるか判定せよ。
解説
サイクルグラフであることとグラフが連結で各頂点の次数が 2 であることと同値なので、それを判定する。
解説
再帰を行うので上限回数を変更します。
import sys
# 再帰の上限回数の変更
sys.setrecursionlimit(10**9)入力を受け取り、グラフの隣接リストを作成します。
# 入力
N,M=map(int, input().split())
# グラフの隣接リストを作成
G=[[] for _ in range(N)]
for _ in range(M):
a,b=map(int,input().split())
# 0-indexed に変換
a-=1
b-=1
G[a].append(b)
G[b].append(a)各頂点の次数が \(2\) であるか判定する。各頂点の次数が \(2\) でないときはNoを出力して終了します。
# 各頂点の次数が 2 でなければ、サイクルにならない
for i in range(N):
if len(G[i])!=2:
print('No')
exit()訪問済みのフラグvisitedを用意します。頂点 \(0 \)からスタートして 深さ優先探索（DFS）を行います。
# 訪問済みのフラグ
visited=[False]*N
# DFS
def dfs(current,past):
visited[current]=True
for next in G[current]:
# 来た道を戻るのはスキップ
if next==past:
continue
# すでに訪問済みの頂点もスキップ
if visited[next]:
continue
dfs(next,current)
# 頂点 0 からスタートして DFS
dfs(0,-1)すべての頂点を訪問していれば連結なのでYesを出力します。連結でなければNoを出力します。
# すべての頂点を訪問していなければ、連結ではない
if all(visited):
print('Yes')
else:
print('No')解答
import sys
# 再帰の上限回数の変更
sys.setrecursionlimit(10**9)
# 入力
N,M=map(int, input().split())
# グラフの隣接リストを作成
G=[[] for _ in range(N)]
for _ in range(M):
a,b=map(int,input().split())
# 0-indexed に変換
a-=1
b-=1
G[a].append(b)
G[b].append(a)
# 各頂点の次数が 2 でなければ、サイクルにならない
for i in range(N):
if len(G[i])!=2:
print('No')
exit()
# 訪問済みのフラグ
visited=[False]*N
# DFS
def dfs(current,past):
visited[current]=True
for next in G[current]:
# 来た道を戻るのはスキップ
if next==past:
continue
# すでに訪問済みの頂点もスキップ
if visited[next]:
continue
dfs(next,current)
# 頂点 0 からスタートして DFS
dfs(0,-1)
# すべての頂点を訪問していなければ、連結ではない
if all(visited):
print('Yes')
else:
print('No')ABC404 D – Goin’ to the Zoo
問題
問題文の要約は以下の通りです。
問題の要約
\(N\) 個の動物園があり、それぞれ入園料が与えられます。また \(M\) 種類の動物がいて、それぞれどの動物園で見られるかが分かっています。各動物を \(2\) 回以上見る必要があるとき、条件を満たす動物園の訪問回数の組み合わせの中で、入園料の合計が最小になるものを求めよ。
解説
同じ動物園に \(3\) 度以上行く必要はないので、各動物園に行く回数が \(2\) 回 以下のものを全探索する。
解説
全ての組み合わせを求めるために、 itertools.product をimportします。
from itertools import product入力を受け取り、動物園の情報を記録します。
# 入力
N,M=map(int,input().split())
C=list(map(int,input().split()))
# 動物園の情報を記録
zoos=[]
for _ in range(M):
K,*A=list(map(int,input().split()))
# 0-indexに変換
zoos.append([a - 1 for a in A])コストの最小値をmin_costで定義します。
# コストの最小値
min_cost = float('inf')動物園の訪問回数の全パターンを全探索するします。（各動物園は 0～2 回訪問）訪問回数の組み合わせはproduct(range(3),repeat=N)で生成できます。各パターンにおいて、すべての動物が合計で \(2\) 回以上見られているかを確認し、条件を満たすパターンの中で、訪問回数 × 入園料の合計が最小のものでコストを更新します。
# 各動物園の訪問回数の組合せを全探索
for visit in product(range(3),repeat=N):
# 各動物に対して、その動物を見た回数を計算
ok = True
for zoo in zoos:
count = sum(visit[z] for z in zoo)
# 動物を見た回数が 2 回より小さいときはFalseにしてループを抜ける
if count < 2:
ok=False
break
# 全ての動物を見たい回数が 2 回以上の時はコストを計算
if ok:
cost=sum(visit[i]*C[i] for i in range(N))
min_cost = min(min_cost, cost)最後に答えを出力します。
# 出力
print(min_cost)解答
from itertools import product
# 入力
N,M=map(int,input().split())
C=list(map(int,input().split()))
# 動物園の情報を記録
zoos=[]
for _ in range(M):
K,*A=list(map(int,input().split()))
# 0-indexに変換
zoos.append([a - 1 for a in A])
# コストの最小値
min_cost = float('inf')
# 各動物園の訪問回数の組合せを全探索
for visit in product(range(3),repeat=N):
# 各動物に対して、その動物を見た回数を計算
ok = True
for zoo in zoos:
count = sum(visit[z] for z in zoo)
# 動物を見た回数が 2 回より小さいときはFalseにしてループを抜ける
if count < 2:
ok=False
break
# 全ての動物を見たい回数が 2 回以上の時はコストを計算
if ok:
cost=sum(visit[i]*C[i] for i in range(N))
min_cost = min(min_cost, cost)
# 出力
print(min_cost)