Atcoder ABC 303解く

20230527 Atcoder ABC contest 303

NS Solutions Corporation Programming Contest 2023（AtCoder Beginner Contest 303） - AtCoder

A問題

意外と時間かかった3回WA出してもうた
最初はandとifの多用で強引に通そうとしたけどandの仕様がよくわからず断念結局2次元配列で管理して not in で判定するのが一番わかりやすかった。

N = int(input())
S = str(input())
T = str(input())

ans = [["0", "o"], ["o", "0"], ["l", "1"], ["1", "l"]]

flg = 1
for n in range(N):
    if S[n] != T[n]:
        if [S[n], T[n]] not in ans:
            flg = 0
                

if flg:
    print("Yes")
else:
    print("No")

B問題

珍しく一発でAC
平方行列を作って隣り合っている同士のところを0→1に変換して最終的に0の数を数えて2で割る

N, M = map(int,input().split())

S = []
for _ in range(N):
    S.append([0 for i in range(N)])

for n in range(N):
    S[n][n] = 1

A = []
for _ in range(M):
    # A.append(list(input().split()))
    a = list(map(int,input().split()))
    for i in range(N - 1):
        y = a[i] - 1
        x = a[i + 1] - 1
        S[y][x] = 1
        S[x][y] = 1

cnt = 0
for n in S:
    for i in n:
        if i == 0:
            cnt += 1

print(cnt // 2)

C問題

提出したコード↓：TLEでタイムアウト

N, M, H, K = map(int, input().split())
S = input()
item = []
for i in range(M):
    item.append(list(map(int,input().split(" "))))

cnt = 0
flg = 1
x, y = 0, 0
while cnt < N:
    H -= 1
    if H < 0:
       flg = 0
       print("No")
       break

    if S[cnt] == "R":
      x += 1
    elif S[cnt] == "L":
      x -= 1
    elif S[cnt] == "U":
      y += 1
    elif S[cnt] == "D":
      y -= 1
    
    cnt += 1
    
    if [x, y] in item and H < K:
        H = K
        item.remove([x, y])

    
if flg:
   print("Yes")

・tupleはイミュータブルだが少し早い。setは集合演算ができる
・while文でなく、orderでfor文を回す
・itemのアクセス時にX＾2を使ってたのかも？pythonの良くないところ出た
・breakでなくexit()でコードを突破できる
・動かし方を辞書型とタプルで表現するとわかりやすい

↓TLEにならない

# setは集合演算(.union/.intersection)が使える
# tupleはlistに比べてイミュータブルである代わりに少し早い
item = set([tuple(map(int, input().split())) for _ in range(M)])

move = {"R":(1,0), "L":(-1, 0), "U":(0,1), "D":(0,-1)}
now = [0, 0]

for order in S:
   walk = move[order]
   H -= 1
   if H < 0:
      print("No")
      exit()
   now[0] += walk[0]
   now[1] += walk[1]
   if tuple(now) in item and H < K:
      H = K
      item.remove(tuple(now))
print("Yes")

D問題

むりぽ。全探索でTLEになりそうということだけわかる。動的計画法を使うらしい
なるほど。ダイクストラ法みたいな感じだ。無理