A問題
解答
1 2 |
s,t = input().split() print(s + " " + "san") |
B問題
方針
- 0時~23時までを全探索
- 各時間から8時間差までの地域の参加可能人数を加えていく
- その合計の最大値を返す
LeetCodeにも類題がある。考え方は近いので練習ができそう。
解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
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 深さ優先探索
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
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
■記事一覧
コメント