AtCoder Beginner Contest 404 を振り返ります
AtCoder Beginner Contest 404（Promotion for Engineer Guild） - AtCoder
今回はD問題まで4問解答でした。レーティングは久々に微増でした。
D問題は解けたんですけども、時間がかかってしまったのが反省です。深さ優先探索の実装がなかなかうまくできなかったので、こういう典型問題はさくっと解いてしまいたいところです。
また、B問題で単純ミスで、一回WAしてしまったのが痛かったかもです。
A - Not Found
アルファベットの26文字分の配列を用意します。 "a","b","c","d"... と探していって、文字列Sに含まれなかった文字を出力すればOKです。
S = list(input())
char_list = list(string.ascii_lowercase) # "a","b","c","d"... の配列
# "a" から順に、含まれない文字を探す
for i in range(len(char_list)):
if char_list[i] not in S:
print(char_list[i])
break
B - Grid Rotation
B問題としては難しかったような...。グリッドの大きさが 100以下ですので、全探索をします。
Sが90度右回転できるので、以下のパターンを求めて、操作回数が最小になるものを求めれば良いです。
- S, Tをそのまま比較し、色が異なる箇所をカウント
- S(90度回転), Tを比較し、色が異なる箇所をカウント
- S(180度回転), Tを比較し、色が異なる箇所をカウント
- S(270度回転), Tを比較し、色が異なる箇所をカウント
以下の2つのメソッドを用意しておけば楽になります。
- グリッド中で、色が異なる箇所をカウントするメソッド
- グリッドを右回転させるメソッド
本番では270度回転を書き忘れて、WAになりました...
N = int(input())
S = []
T = []
for i in range(N):
s = input()
S.append(s)
for i in range(N):
t = input()
T.append(t)
# 配列 s, t の中で、色が異なる箇所をカウントする
def count(s, t):
count = 0
for i in range(N):
for j in range(N):
if s[i][j] != t[i][j]:
count += 1
return count
# グリッドを右回転させる
def rotate_right(s):
new_s = []
for i in range(N):
line = []
for j in range(N):
line.append(s[N - j - 1][i])
new_s.append(line)
return new_s
#［回転なし、90回転, 180回転, 270回転]の中で最小値を求める
answer = INF
answer = min(answer, count(S, T))
answer = min(answer, count(rotate_right(S), T) + 1)
answer = min(answer, count(rotate_right(rotate_right(S)), T) + 2)
answer = min(answer, count(rotate_right(rotate_right(rotate_right(S))), T) + 3)
print(answer)
C - Cycle Graph?
以下のように求めれば、答えが出ると考えて実装しました。
[1] # 1から始める
[1, 3] # 1から行ける頂点は[3,4] なので、3を追加
[1, 3, 2] # 3から行ける頂点は[1,2] なので、2を追加 (1は追加済み)
[1, 3, 2, 4] # 2から行ける頂点は[3,4] なので、4を追加 (3は追加済み)
先頭と末尾をつなぐ辺があれば、サイクルグラフ=Yes。なければ=No.
追加済判定を楽にするため、追加済頂点を set で管理します。
あと、サイクルグラフなら、頂点から伸びる辺はかならず2つになるので、そこもチェックするようにしました。
N, M = map(int, input().split())
path = defaultdict(set)
for i in range(M):
a, b = map(int, input().split())
path[a].add(b)
path[b].add(a)
used_set = set() # 使用済頂点を管理するSet
queue = deque() # サイクルグラフをdequeで管理
# 頂点1から始める
queue.append(1)
used_set.add(1)
is_loop = True
while True:
current = queue[-1]
next_set = path[current]
# ある頂点から行ける頂点は2つ
if len(next_set) != 2:
is_loop = False
break
# 次の頂点に行けなくなったら、ループ終了
exist = False
for next in next_set:
# 次に行ける頂点があれば、ループ続行
if next not in used_set:
exist = True
queue.append(next)
used_set.add(next)
break
if exist == False:
break
if is_loop == False:
print("No")
exit()
# キューの中にN頂点が入っていて、最初と最後をつなぐパスがあればYes
if len(queue) == N:
first = queue[0]
last = queue[-1]
if first in path[last]:
print("Yes")
exit()
print("No")
D - Goin' to the Zoo
データの持ち方を変えて、動物園になんの動物がいるかを考えます。
# 入力例 1 の場合
zoo 1 = [1, 1, 1] (動物1,2,3がいる)
zoo 2 = [0, 1, 0] (動物2がいる)
zoo 3 = [1, 0, 1] (動物1,3がいる)
zoo 4 = [1, 1, 0] (動物1,2がいる)
あとは、それぞれの動物園を0回〜2回見た場合のパターンを全探索しまして...
Zoo1 を (0回 or 1回 or 2回)見た
Zoo2 を (0回 or 1回 or 2回)見た
Zoo3 を (0回 or 1回 or 2回)見た
...
Zoo10 を (0回 or 1回 or 2回)見た
最終的に、全動物を2回以上見ていればokです。
計算量は 3**10=59049 なので、十分間に合いそうです。
全探索には深さ優先探索を使用しました。
sys.setrecursionlimit(10 ** 8)
INF = 10 ** 18
N, M = map(int, input().split())
C = list(map(int, input().split()))
C.insert(0, 0)
# 動物園ごとに、いる動物の配列
zoo = [[0] * (M) for _ in range(N + 1)]
for i in range(M):
KA = list(map(int, input().split()))
for j in range(1, len(KA)):
zoo[KA[j]][i] = 1
min_cost = INF # コストの最小値
current_saw = [0] * (M) # 動物を見た回数を記録する配列
# 深さ優先探索
def dfs(zoo_index, current_cost):
global min_cost
# 動物園を見終わって、すべての動物を2回以上見ていればok
if zoo_index == N:
if min(current_saw) >= 2:
min_cost = min(min_cost, current_cost)
return
# 次の動物園を(0回 or 1回 or 2回)見るパターンを探索
next_zoo = zoo[zoo_index+1]
for next_visit_count in range(0, 3):
for i in range(M ):
current_saw[i] += next_zoo[i] * next_visit_count
dfs(zoo_index + 1, current_cost + C[zoo_index + 1] * next_visit_count)
for i in range(M ):
current_saw[i] -= next_zoo[i] * next_visit_count
# 探索開始
dfs(0, 0)
print(min_cost)