ABC303に参加しました

概要

　今回はAtcoder Beginner Contest 303（2023年5月27日21:00~22:40）に参加したので振り返りがてら記事を書きます。

A問題

コメント

• 愚直にif文で場合分けした
• どっかで見た、「1をl、0をoにあらかじめ置換しておいてSとTが一致するか判定」というのもよいなと思った

自分の実装

ABC_303_A.py

N = int(input())
S,T = input(),input()
ans = 1

for i in range(N):
  if (S[i] != T[i]):
    if((S[i] == "1" and T[i] == "l") or (S[i] == "l" and T[i] == "1")):
      ans = 1
    elif((S[i] == "0" and T[i] == "o") or (S[i] == "o" and T[i] == "0")):
      ans = 1
    else:
      ans = 0
      print("No")
      exit()
        
if ans == 1:
  print("Yes")

B問題

コメント

• NとMが高々50だったので、2重ループの計算量でも特に問題なさそう
• 自分と隣り合ったことがある人の情報を記録する行列relationを用意して、隣り合ったことがあれば1、そうでなければ0になるようにして、最後にその数をカウントするという方針をとった
• 対称性を考えて2で割るのを忘れずに

自分の実装

ABC_303_B.py

N,M = map(int,input().split())
a = [list(map(int, input().split())) for l in range(M)]
relation = [[1] * N for i in range(N)]
count = 0

for i in range(N):
  relation[i][i] = 0

for i in range(M):
  for j in range(N-1):
    relation[a[i][j]-1][a[i][j+1]-1] = 0
    relation[a[i][j+1]-1][a[i][j]-1] = 0

for i in range(N):
  for j in range(N):
    count += relation[i][j]
    
print(count//2)

C問題

コメント

• 制約が $\leq 2×10^5$ となっていて計算量を考える必要が出てきそうだなとか考えていた
• 問題の指示を愚直に実装していけたかなーって思ったらWAでハマる
• 途中でアイテムを使用した場合に配列からRemoveしてないことに気づいて直すもTLEで手詰まり
• 解説を見てSetを使えば行けるらしいことを知る

自分の実装(TLE)

ABC_303_C.py

N,M,H,K = map(int,input().split())
S = input()
xy = [list(map(int, input().split())) for l in range(M)]
current_tak = [0,0]

for i in range(N):
  if(N <= H):
    exit()
  
  else:
    if (S[i] == "R"):
      current_tak[0] += 1
      H -= 1
    elif (S[i] == "L"):
      current_tak[0] -= 1
      H -= 1
    elif (S[i] == "U"):
      current_tak[1] += 1
      H -= 1
    elif (S[i] == "D"):
      current_tak[1] -= 1
      H -= 1

    if (current_tak in xy) and (H >= 0) and (H < K): #こいつがTLEの原因っぽい
      H = K
      xy.remove(current_tak)
    elif (H < 0):
      print("No")
      exit()

if (H >= 0):
  print("Yes")

感想

計算量の壁にぶち当たる
そろそろC++も手を付けていきたい
Listとsetの計算量の違いに関しては、この記事がとても分かりやすかったです。
https://qiita.com/kitadakyou/items/6f877edd263f097e78f4