前回の振り返り
今日はABC436開催日だったので参加結果を振り返る
今週はA,B,C,Dの4完(0ペナ)
A
目的の文字列の長さNから
Sの長さを引いてた数だけ
oを左から足す
ソースコード
main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)
def main():
N = rI()
S = rS()
ans = "o"*(N-len(S))+S
print(ans)
if __name__ == '__main__':
main()
B
魔方陣のプログラムはインターネットにたくさん転がってるので検索して出てきたやつを参考にコーディング
コンテスト終了後にソースコード
main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)
def main():
N = rI()
A = [[0] * N for _ in range(N)]
i = 0
j = (N-1) // 2
for k in range(1, N**2 + 1):
A[i][j] = k
new_i = (i - 1) % N
new_j = (j + 1) % N
if A[new_i][new_j] != 0:
i = (i + 1) % N
else:
i = new_i
j = new_j
for a in A:
print(*a)
if __name__ == '__main__':
main()
C
ブロックが置かれているマスの座標をsetで管理
起きたい場所のブロックが他のブロックの座標と被っていなければ追加する
ソースコード
main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)
dy = [0, 1, 0, 1]
dx = [0, 0, 1, 1]
def main():
N, M = rLI()
S = set()
ans = 0
for _ in range(M):
R, C = rLI()
for di in range(4):
p = R + dy[di], C + dx[di]
if p in S:
break
else:
ans += 1
for di in range(4):S.add((R + dy[di], C + dx[di]))
print(ans)
if __name__ == '__main__':
main()
D
gridBFSにワープポイントが増えたイメージ。
先にワープポイントを管理して
今いる座標がワープポイントだったらいつもの上下左右探索に加えてワープ先の座標も探索する。
1回つかったワープポイントの種類はもう使わないようにする。
ソースコード
main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)
wp = 'abcdefghijklmnopqrstuvwxyz'
def main():
H, W = rLI()
S = [list(rS()) for _ in range(H)]
warp = [set() for _ in range(26)]
warped = set()
for i in range(H):
for j in range(W):
s = S[i][j]
if s in wp:
k = ord(s) - ord('a')
warp[k].add((i,j))
# err(*[len(w) for w in warp])
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
def out_of_bounds(y, x, h, w):
return y < 0 or y >= h or x < 0 or x >= w
def bfs(i, j, h, w, grid):
q = deque([(i, j)])
dist = [[-1] * w for _ in range(h)]
visited = [[False] * w for _ in range(h)]
dist[i][j] = 0
visited[i][j] = True
while q:
y, x = q.popleft()
# if y==H-1 and x==W-1:
# break
# err(y,x)
for di in range(4):
ny, nx = y + dy[di], x + dx[di]
if not out_of_bounds(ny, nx, h, w) and grid[ny][nx] != "#" and not visited[ny][nx]:
dist[ny][nx] = dist[y][x] + 1
visited[ny][nx] = True
q.append((ny, nx))
if (s:=grid[y][x]) in wp and s not in warped:
k = ord(s) - ord('a')
warped.add(s)
warp[k].remove((y,x))
for ny,nx in warp[k]:
if not out_of_bounds(ny, nx, h, w) and grid[ny][nx] != "#" and not visited[ny][nx]:
dist[ny][nx] = dist[y][x] + 1
visited[ny][nx] = True
q.append((ny, nx))
# err(y,x,len(q))
return dist
d = bfs(0,0,H,W,S)
ans = d[-1][-1]
print(ans)
# print(*ans)
# print('Yes' if ans else 'No')
if __name__ == '__main__':
main()
E
転倒数とか互換の積とか悩みまくったけど思いつかなかった
- 若干グラフの匂いもしてたけどどうやらそっち方面だったようだ。
F
星空って綺麗だよね。
G
10**18とかいうオーダーに戦慄
感想
久々にratedで参加したけど4完できて嬉しい。
そろそろE問題も射程圏にいれた精進が必要になってきたかも