体調不調により不参加
A - The bottom of the ninth
リンク：A - The bottom of the ninth (atcoder.jp)
概要：野球をしていて9回表終了までの点数が配列と
で与えられます。9回裏（チーム
の攻撃）で逆転サヨナラするために必要な点数を教えてね
チームが勝つためにはこの回でチーム
の総得点（
）を越える必要があります。
チームの得点は
なので、両チームの総得点の差分+1点をこの回で得点できれば勝利することができます。
以下のコードでは入力をリストとして受け取ると同時に合計を計算させています。
#ABC351 A - The bottom of the ninth
A = sum(list(map(int, input().split())))
B = sum(list(map(int, input().split())))
print(A-B+1) 提出リンク：提出 #52939398 - AtCoder Beginner Contest 351
B - Spot the Difference
リンク：B - Spot the Difference (atcoder.jp)
概要：文字列からなるグリッドが2つ与えられます。両者を比較すると1か所だけ異なる場所があるので座標を教えてね
問題文そのままです。
二次元盤面を受け取って全文字を探索し、異なる点を出力します。
入力の受け取りが0-indexed、要求される答えは1-indexedなので最後に1を足すことを忘れずに。
#ABC351 B - Spot the Difference
N = int(input())
A = []
for _ in range(N):
a = input()
A.append(a)
for i in range(N):
a = A[i]
b = input()
for j in range(N):
if a[j] != b[j]:
print(i+1, j+1) 提出リンク：提出 #52939558 - AtCoder Beginner Contest 351
C - Merge the balls
リンク：C - Merge the balls (atcoder.jp)
概要：様々な大きさのボールがやってきます。次の操作を行って最終的なボールの数を教えてね
- ボールが1個なら操作終了
- ボールが複数あり同じサイズのボールが2つ連続する場合はサイズ＋１のボールに置き換える
- ボールが複数あり隣り合うボールすべて違うサイズなら操作終了
なので愚直に処理するとTLEになるりそうな気がするけど順番が関係するのでそのまま処理するしかなさそう。
ひとまず問題文そのまま書いてみたところACできました。
計算量をどう考えたらいいのかよくわかりませんが、ボールを結合する操作は最大回しかしないので
になるのでしょうか。
問題文ではボールのサイズはとなっていますが
で管理しても変わりありません。
末尾にあるボールの取り出しはpop(-1)で行います。
（2回続けてpopするので両方とも末尾から取り出す形になります。）
配列に対する長さの取得（len）、末尾の取り出し（pop）、末尾に追加（append）いずれも計算量はです。
取り出すときと戻すときの順番に気を付ければそこまで難しくはないと思います。
#ABC351 C - Merge the balls
N = int(input())
A = list(map(int, input().split()))
ans = []
for i in range(N):
ans.append(A[i])
#ボールが2個以上なら操作を試みる
while len(ans) > 1:
#並び順で後になるボールをato、前になるボールをmaeとして取り出し
ato = ans.pop(-1)
mae = ans.pop(-1)
if mae != ato:
#サイズが違うなら元の順番で戻す
ans.append(mae)
ans.append(ato)
break
else:
#同じサイズならサイズ+1を1つだけ追加する
ans.append(mae+1)
print(len(ans)) 提出リンク：提出 #52939741 - AtCoder Beginner Contest 351
D - Grid and Magnet
リンク：D - Grid and Magnet (atcoder.jp)
概要：条件付き二次元盤面で各マスから最大何マス移動できるか探索して、その最大数を教えてね
いつもの壁と通路の二次元盤面ですが、今回は壁が磁石になっていて壁に隣接するマスに侵入はできますが脱出はできないという問題設定です。
また移動できる最大距離ではなく、全方位で合計何マス動けるか（＝自由度）を問われています。
二次元盤面、探索ということで幅優先探索を使います。
基本方針は以下のようにします。
- 現在地が通路であれば探索開始
- 隣接する上下左右4マスを見て壁でなければ移動可能ということで自由度+1
- 移動した先が壁に隣接するマスであればそれ以上移動はしない
- 互いに移動可能なマスであれば自由度は同じなので、一度踏んだマスを記録しておいて2回以上同じ探索をしないようにする
ABC348Dで幅優先探索を書いていたので流用してジャッジ・・・TLE
#ABC351 D - Grid and Magnet
from collections import deque
def bfs(grid, sx, sy):
DX = [1,-1,0,0]
DY = [0,0,1,-1]
H = len(grid)
W = len(grid[0])
q = deque()
q.append((sx, sy))
seen = [[False for j in range(W)] for i in range(H)]
seen[sx][sy] = True
while q:
x, y = q.popleft()
if grid[x][y] == 'N':
continue
else:
for dx, dy in zip(DX,DY):
xt, yt = x+dx, y+dy
if xt < 0 or H-1 < xt or yt < 0 or W-1 < yt:
continue
if grid[xt][yt] == '#':
continue
if seen[xt][yt] == True :
continue
else:
DOF[i][j] += 1
visited[xt][yt] = True
seen[xt][yt] = True
q.append((xt, yt))
H, W = map(int, input().split())
grid = []
for _ in range(H):
grid.append(input())
#壁に隣接する部分を'N'として識別しやすくする
mas = [[0 for j in range(W)] for i in range(H)]
DX = [1,-1,0,0]
DY = [0,0,1,-1]
for x in range(H):
for y in range(W):
if grid[x][y] == '#':
mas[x][y] = 1
for dx, dy in zip(DX,DY):
xt, yt = x+dx, y+dy
if xt < 0 or H-1 < xt or yt < 0 or W-1 < yt:
continue
if grid[xt][yt] == '#':
continue
else:
mas[xt][yt] = 2
grid2 = []
for x in range(H):
s = ''
for y in range(W):
if mas[x][y] == 0:
s += '.'
if mas[x][y] == 1:
s += '#'
if mas[x][y] == 2:
s += 'N'
grid2.append(s)
DOF = [[1 for j in range(W)] for i in range(H)]
visited = [[False for j in range(W)] for i in range(H)]
for i in range(H):
for j in range(W):
if visited[i][j] == False:
if grid2[i][j] == '#':
continue
if grid2[i][j] == 'N':
DOF[i][j] = 1
else:
bfs(grid2, i, j)
ans = 0
for i in range(H):
for j in range(W):
ans = max(ans, DOF[i][j])
print(ans) 提出リンク：提出 #52945183 - AtCoder Beginner Contest 351
いろんなパターンで確認しても重複して探索はしていないのでそれ以外の部分の定数倍でTLEしてるっぽい。一晩寝て考える。
ひとまずグリッドを受け取った後に壁隣接部分を特定しやすいように処理している部分を消してみる・・・TLE。
もしかして探索済をマークする配列の作成に毎回
かかるのが重たいのでは？と思い集合型（set）に変えてみるとAC。
#ABC351 D - Grid and Magnet
def magnet(grid, x, y):
global H
global W
div = [(1,0), (-1,0), (0,1), (0,-1)]
magnet = False
for dx, dy in div:
xt, yt = x+dx, y+dy
if xt < 0 or H-1 < xt or yt < 0 or W-1 < yt:
continue
if grid[xt][yt] == '#':
magnet = True
if magnet:
return True
from collections import deque
H, W = map(int, input().split())
grid = []
for _ in range(H):
grid.append(input())
DOF = [[0]*W for _ in range(H)]
visited = [[False]*W for _ in range(H)]
ans = 1
for i in range(H):
for j in range(W):
if visited[i][j] == False:
if grid[i][j] == '#':
continue
if magnet(grid, i, j):
DOF[i][j] = 1
continue
else:
DOF[i][j] += 1
div = [(1,0), (-1,0), (0,1), (0,-1)]
q = deque()
q.append((i, j))
#探索済をマークする部分を配列からsetに変更
seen = set()
seen.add((i, j))
visited[i][j] = True
while q:
x, y = q.popleft()
if magnet(grid, x, y):
continue
for dx, dy in div:
xt, yt = x+dx, y+dy
if xt < 0 or H-1 < xt or yt < 0 or W-1 < yt:
continue
if grid[xt][yt] == '#':
continue
if (xt, yt) in seen:
continue
DOF[i][j] += 1
visited[xt][yt] = True
seen.add((xt, yt))
q.append((xt, yt))
ans = max(DOF[i][j], ans)
print(ans)
#print(DOF)
#print(visited)提出リンク：提出 #52999641 - AtCoder Beginner Contest 351
感想
本番出てたら30分でA～Cの3完というところでしょうか。
幅優先探索バグらせがちなので上手になりたい。
以下の学びがあったので次からは気を付けよう。
- 何度もBFSする場合は探索済の管理を配列ではなくsetで行う
- 上下左右4マスを見るときにin zip(DX、DY)としていたが（TLEしたコード）、zipを使わないほうが微妙に速い
ところでこのWA、TLEの数は何ですか？？？？
