【ABC325】Atcoder Beginner Contest325 A・B・C問題解答・解説【Python】

A問題
1. 解答
B問題
1. 方針
2. 解答
C問題
補足・参考・感想

A問題

解答

s,t = input().split()
print(s + " " + "san")

1 2	s,t = input().split() print(s + " " + "san")

B問題

方針

0時～23時までを全探索
各時間から8時間差までの地域の参加可能人数を加えていく
その合計の最大値を返す

LeetCodeにも類題がある。考え方は近いので練習ができそう。

解答

n = int(input())
#時間帯ごとの参加可能な人数を保持するのリスト
participant_by_time_zone = [0 for _ in range(24)]
#各時間帯の参加可能な人数をリストの各要素の値として加えていく
for i in range(0, n):
    w, x = map(int, input().split())
    participant_by_time_zone[x] += w

available = 0
#0時～23時までの各時間帯を全探索
for hour in range(24):
    tmp_available = 0
    #各時間帯からさらに8時間差までの地域の人数を合計する
    for interval in range(9):
        #intervalが0~8まで変化する。
        #17時以降は8時間差の地域を含めると翌日の時間を含むが、
        #%で剰余を取ることで24時を越えた時差8時間以内の地域を含めることができる
        tmp_available += participant_by_time_zone[(hour+interval) % 24]
    available = max(available, tmp_available)

n = int(input())

#時間帯ごとの参加可能な人数を保持するのリスト

participant_by_time_zone = [0 for _ in range(24)]

#各時間帯の参加可能な人数をリストの各要素の値として加えていく

for i in range(0, n):

w, x = map(int, input().split())

participant_by_time_zone[x] += w

available = 0

#0時～23時までの各時間帯を全探索

for hour in range(24):

tmp_available = 0

#各時間帯からさらに8時間差までの地域の人数を合計する

for interval in range(9):

#intervalが0~8まで変化する。

#17時以降は8時間差の地域を含めると翌日の時間を含むが、

#%で剰余を取ることで24時を越えた時差8時間以内の地域を含めることができる

tmp_available += participant_by_time_zone[(hour+interval) % 24]

available = max(available, tmp_available)

C問題

方針

H行W列の座標であるgridを入力を受け取り作成する
各座標を調べて#だったときに3の処理を幅優先探索か深さ優先探索で行う
#、つまりセンサーのあるマスは上下左右斜めの8座標も#であるか同時に調べて、” . “に置き換えて、すべてまとめて1個としてカウントする
#の数を表示する

解答1：DFS　深さ優先探索

def helper(row, column):
    #gridの範囲内か判定
    if 0<=row<h and 0<=column<w:
        if grid[row][column] == "#":
            # #を.に変える
            grid[row][column] = "."
            #上下左右斜めのセンサーを調べる
            helper(row+1, column)
            helper(row-1, column)
            helper(row, column+1)
            helper(row, column-1)
            helper(row+1, column+1)
            helper(row+1, column-1)
            helper(row-1, column+1)
            helper(row-1, column-1)
    return 1

h,w = map(int, input().split())
grid = []
for row in range(h):
    s = input()
    s = list(s)
    grid.append(s)

#print(grid)
number_of_sensors = 0
for row in range(h):
    for column in range(w):
        if grid[row][column] == "#":
            number_of_sensors += helper(row, column)

print(number_of_sensors)

def helper(row, column):

#gridの範囲内か判定

if 0<=row<h and 0<=column<w:

if grid[row][column] == "#":

# #を.に変える

grid[row][column] = "."

#上下左右斜めのセンサーを調べる

helper(row+1, column)

helper(row-1, column)

helper(row, column+1)

helper(row, column-1)

helper(row+1, column+1)

helper(row+1, column-1)

helper(row-1, column+1)

helper(row-1, column-1)

return 1

h,w = map(int, input().split())

grid = []

for row in range(h):

s = input()

s = list(s)

grid.append(s)

#print(grid)

number_of_sensors = 0

for row in range(h):

for column in range(w):

if grid[row][column] == "#":

number_of_sensors += helper(row, column)

print(number_of_sensors)

これだとエラーが発生して不正解になる。。。

解答2：BFS

def DFS(row, column):
    #gridの範囲内か判定
    if 0<=row<h and 0<=column<w:
        if grid[row][column] == "#":
            # #を.に変える
            grid[row][column] = "."
            #上下左右斜めのセンサーを調べる
            DFS(row+1, column)
            DFS(row-1, column)
            DFS(row, column+1)
            DFS(row, column-1)
            DFS(row+1, column+1)
            DFS(row+1, column-1)
            DFS(row-1, column+1)
            DFS(row-1, column-1)
    return 1

#幅優先探索
def BFS(row, column) -> int:
    from collections import deque
    #キューに追加
    queue = deque()
    queue.append((row, column))
    #キューの各要素を調べる
    while queue:
        row, column = queue.popleft()
        #grid内の座標の場合に以降の処理を行う
        if 0<=row<h and 0<=column<w:
            #現在座標が#、つまりセンサーだった場合、上下左右斜めの各座標をキューに加える。
            #また、最後に現在座標を.に書き換えて、再訪問時の再加算を防ぐ。
            if grid[row][column] == "#":
                queue.append((row+1, column))
                queue.append((row-1, column))
                queue.append((row, column+1))
                queue.append((row, column-1))
                queue.append((row+1, column+1))
                queue.append((row+1, column-1))
                queue.append((row-1, column+1))
                queue.append((row-1, column-1))
                grid[row][column] = "."
    #上下左右斜めの分も全て探索後、1つのセンサーとみなすので1を返す
    return 1

#入力を受け取り、H行W列の座標であるgridを作成
h,w = map(int, input().split())
grid = []
for row in range(h):
    s = input()
   #sは1つの文字列なので、リストにして,区切りにする
    s = list(s)
    grid.append(s)


number_of_sensors = 0
#各座標が#だったら幅優先探索を実行する。
for row in range(h):
    for column in range(w):
        if grid[row][column] == "#":
            #number_of_sensors += DFS(row, column)
            number_of_sensors += BFS(row, column)

print(number_of_sensors)こ

def DFS(row, column):

#gridの範囲内か判定

if 0<=row<h and 0<=column<w:

if grid[row][column] == "#":

# #を.に変える

grid[row][column] = "."

#上下左右斜めのセンサーを調べる

DFS(row+1, column)

DFS(row-1, column)

DFS(row, column+1)

DFS(row, column-1)

DFS(row+1, column+1)

DFS(row+1, column-1)

DFS(row-1, column+1)

DFS(row-1, column-1)

return 1

#幅優先探索

def BFS(row, column) -> int:

from collections import deque

#キューに追加

queue = deque()

queue.append((row, column))

#キューの各要素を調べる

while queue:

row, column = queue.popleft()

#grid内の座標の場合に以降の処理を行う

if 0<=row<h and 0<=column<w:

#現在座標が#、つまりセンサーだった場合、上下左右斜めの各座標をキューに加える。

#また、最後に現在座標を.に書き換えて、再訪問時の再加算を防ぐ。

if grid[row][column] == "#":

queue.append((row+1, column))

queue.append((row-1, column))

queue.append((row, column+1))

queue.append((row, column-1))

queue.append((row+1, column+1))

queue.append((row+1, column-1))

queue.append((row-1, column+1))

queue.append((row-1, column-1))

grid[row][column] = "."

#上下左右斜めの分も全て探索後、1つのセンサーとみなすので1を返す

return 1

#入力を受け取り、H行W列の座標であるgridを作成

h,w = map(int, input().split())

grid = []

for row in range(h):

s = input()

#sは1つの文字列なので、リストにして,区切りにする

s = list(s)

grid.append(s)

number_of_sensors = 0

#各座標が#だったら幅優先探索を実行する。

for row in range(h):

for column in range(w):

if grid[row][column] == "#":

#number_of_sensors += DFS(row, column)

number_of_sensors += BFS(row, column)

print(number_of_sensors)こ

こちらはACになった。

補足・参考・感想

■C問題の類題：LeetCode

200. Number of Islands

695. Max Area of Island

733. Flood Fill

■記事一覧

AtCoder Beginner Contest 解答・解説記事一覧

A問題

解答

B問題

方針

解答

C問題

方針

解答1：DFS 深さ優先探索

解答2：BFS

補足・参考・感想

コメント

解答1：DFS　深さ優先探索