どうもこんにちは！
今週のコンテストはCまで完答、振り返りCもまで。
Dは事前に文字とワープ先の一覧を作った上で幅優先探索、できるだけ計算量を落とす手間を入れたんですが、テストケース51個のうち最後の1個がTLEとなり解消できず。。どんなテストケースやったんか気になります。
※ 2025/12/14 D問題を追加しました
問題と公式の解説のリンク
問題は以下のリンクから。
A - o-padding -
問題
整数nと文字列sが与えられます。文字数がn文字になるまでsの先頭にoを追加し、その文字列を出力する問題。
考え方とコード
文字数の不足数を計算してその数だけoを足した文字列を出力するとしました。
n = int(input())
s = input()
print('o'*(n-len(s))+s)
B - Magic Square -
問題
整数nが与えられます。n行n列のマスに以下の手順で数字を書き込み、その結果を出力する問題。
- 座標(0,(n-1) // 2)のマスに1を書き込む
- 前回書き込んだマスを(r,c)、書き込んだ整数をkとします。座標((r-1) % n, (c+1) % n)のマスが未記入ならそこにk+1を、記入済みなら((r+1) % n, c)にk+1を書き込む。
- 手順2を$n^2-1$回繰り返す
考え方とコード
2次元リストを使って素直に手順通りの実装をしました。
n = int(input())
ans = [[0]*n for _ in range(n)]
ans[0][(n-1)//2] = 1
r,c = 0, (n-1)//2
k = 2
while k < n**2+1:
x, y = (r-1) % n, (c+1) % n
if ans[x][y] == 0:
ans[x][y] = k
r, c = x, y
else:
ans[(r+1) % n][c] = k
r, c = (r+1) % n, c
k += 1
for i in ans:
print(*i)
C - 2x2 Placing -
問題
整数n,mとm個の座標(r,c)が与えられます。n行n列のマスがあり、m個のブロックを配置するとします。ブロックの大きさは2マス×2マスで、与えられる座標はブロックの左上の座標です。
ブロックは配置したい座標の4マスすべてに何も無いときのみ配置できるとするとき、配置できる個数を出力する問題。
なおnの最大は$10^9$,mの最大は$2 × 10^5$です。
考え方とコード
1マスごとにブロックがあるかないかを保持しながら計算しようとした場合、nの数が多いとプログラムが実行できませんでした。
そこで、ブロックを配置済みの座標を集合で持つとして、配置したいブロックが収まる座標すべてが集合に含まれていない場合は配置できるとし、そのブロックの座標を集合に追加していくという形にしました。
n,m = map(int,input().split())
ans = 0
b = set()
for _ in range(m):
r,c = map(int,input().split())
if (r,c) not in b and (r+1,c) not in b and (r,c+1) not in b and (r+1,c+1) not in b:
ans += 1
b.add((r,c))
b.add((r+1,c))
b.add((r,c+1))
b.add((r+1,c+1))
print(ans)
--- 2025/12/14追記 ---
D - Teleport Maze -
問題
H × W のマス目からなる迷路が与えられるので、一番左上のマスから一番右下のマスへの到達可否と到達可能であれば最小の移動数を出力する問題。(Pythonだと座標(0,0)から座標(H-1,W-1))
移動関連の情報は以下。
- 迷路は空きマス、壁マス、英文字で表現するワープマスで構成
- 壁マス以外は上下左右に1回の行動で1マス移動可能、壁マスおよび迷路外には進入不可
- ワープマスでは同じ英文字の座標に1回の行動でワープ可能
考え方とコード
英文字ごとの座標を事前に辞書で持ったうえで、迷路を幅優先探索で探索しました。未ワープの文字のマスではワープ先の座標を辞書から引き出して移動数を更新します。
なお、計算量削減のためにワープ済の文字は無視します。幅優先探索で最短距離を順番に辿っているので、別ルートでワープ済の文字のマスにきても、先にワープして着く方が最短距離ですね。
余談ですが、コンテスト中に最後1個のテストケースだけTLEでしたが、ワープ済みの文字に着くたびに何度もワープする処理しているのが原因のようでした。
from collections import defaultdict,deque
UNVISITED = 10**9
# 幅優先探索で隣接するマスへの移動処理
def check_move(x,y,dx,dy):
if 0 <= x+dx < h and 0 <= y+dy < w and m[x+dx][y+dy] != '#' \
and steps[x+dx][y+dy] > steps[x][y] + 1:
steps[x+dx][y+dy] = steps[x][y] + 1
q.append((x+dx,y+dy))
h,w = map(int,input().split())
# 地図の取得と英文字ごとの座標を事前取得
m = []
warp = defaultdict(list)
warped = set() # ワープ済の文字を管理
for i in range(h):
tmp = list(input())
m.append(tmp)
for j in range(w):
if tmp[j] not in ('.','#'):
warp[m[i][j]].append((i,j))
steps = [[UNVISITED] * w for _ in range(h)]
q = deque()
q.append((0,0))
steps[0][0] = 0
dx = [1,-1,0,0]
dy = [0,0,1,-1]
while q:
x,y = q.popleft()
# 対象がワープマスならワープ先の座標の移動数を更新
# ワープ済みの文字のときは無視
if m[x][y] not in ('.','#') and m[x][y] not in warped:
warped.add(m[x][y])
for cx,cy in warp[m[x][y]]:
if steps[cx][cy] > steps[x][y] + 1:
steps[cx][cy] = steps[x][y] + 1
q.append((cx,cy))
# 隣接マスへの移動
for i in range(4):
check_move(x,y,dx[i],dy[i])
if steps[h-1][w-1] != UNVISITED:
break
print(steps[h-1][w-1] if steps[h-1][w-1] != UNVISITED else -1)
--- 追記ここまで ---
ではでは。