どうもこんにちは！
今週もAtCoderのコンテストに参加できたので、記録がてら振り返ります。
今回はBまで完答。CはよくわからずDの方が解けるかもと思い取り組んだんですが解答できず。
問題
問題は以下のリンクから。取り組めたA,Bを振り返ります。
A - ABC400 Party -
ABC400回記念？ということで、400人を与えられた正の整数Aを使ってA行B列に並べることができるかを判定する問題。シンプルに与えられた正の整数で400を割れるかを判定すればよいですね。
n = int(input())
print(400 // n if 400 % n == 0 else -1)
B - Sum of Geometric Series -
与えられた正の整数n,mを使って、$X = \sum_{i=0}^{m} n^i$を計算し、Xが$10^9$以下ならXを、超えるならinfを出力するという問題。
シンプルに数列を足し合わせて、結果にあわせて出力を変えるとしました。
n,m = map(int,input().split())
ans = 0
for i in range(m+1):
ans += n ** i
print("inf" if ans > 10 ** 9 else ans)
C - 2^a b^2 -
1以上与えられる正の整数n以下の整数のうち、正の整数の組(a,b)を使って$X = 2^a * 2^b$とできる整数の数を答える問題。
解法が何も思いつかずパスしたんですが、例えば3の2乗かつ2の乗数、次は5の2乗かつ2の乗数というように、2乗とする数を増やしながら数字を探していく方向なら計算量も少なく検索できたんでしょうか。
D - Takahashi the Wall Breaker -
縦がhマス、横がwマスのグリッドで、中身は道か壁となっています。与えられるスタート座標からゴール座標に行くにあたって、壁を最小で何回壊せば到達できるかという問題。壁を壊す場合は上下左右のいずれかの方向で、最大2マスまで破壊可能という条件です。
コンテスト中に考えたのは、以下の手順。
・スタート位置から到達可能な座標を幅優先探索で取得する。
・ゴール座標から見て、到達可能な座標のうちもっとも近い位置を取得して、壁を壊す回数を算出する。
で、実際書いたコードが以下ですがTLEとなるケースがあり完答できていません。また、冷静に考えるとこの手順はスタートとゴールをつなぐ道が壁で途切れているだけのケースを考えられていません。道を途切れさせている壁を1回壊せば到達できる場合でも、その壁の位置がゴールから遠いほど複数回壊す結果になるはず、というわけです。
長いし間違っているので折りたたみ
from collections import deque
h,w = map(int,input().split())
grid = [list(input()) for _ in range(h)]
sy,sx,gy,gx = map(int,input().split())
q = deque()
q.append((sy-1,sx-1))
reach = [[-1]*w for _ in range(h)]
reach[sy-1][sx-1] = 0
while q:
ny,nx = q.popleft()
for dy,dx in ((-1,0),(1,0),(0,-1),(0,1)):
if (0 <= ny+dy < h and 0 <= nx+dx < w):
if grid[ny+dy][nx+dx] != "#" and reach[ny+dy][nx+dx] == -1:
grid[ny+dy][nx+dx] = "*"
reach[ny+dy][nx+dx] = reach[ny][nx] + 1
q.append((ny+dy,nx+dx))
if reach[gy-1][gx-1] >= 0:
print(0)
else:
ans = 1
s = False
q = deque()
q.append((gy-1,gx-1))
while True:
y,x = q.popleft()
for dy,dx in ( (-1,0), (-2,0), (2,0), (1,0), (0,-1), (0,-2), (0,1), (0,2)):
if (0 <= y+dy < h and 0 <= x+dx < w):
if reach[y+dy][x+dx] != -1:
s = True
break
else:
q.append((y+dy,x+dx))
if s == True:
break
print(ans)
おわりに
解説見て復習して次に備えます。
ではでは。