ABC 303 備忘録 #AtCoder

概要

　今回はABC303（2023年5月27日21:00~22:40）について実装上のポイントと自分の実装についてコメントしていきたいと思う。

A問題

ポイント

3つの条件について、一度でもいずれかを満たさない場合はNoとなるようにする
ans = 'Yes'としておき、条件分岐で変化させる

自分の実装

ABC_303_A.py

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

ans = 'Yes'

for i in range(N):
    if S[i] == T[i]:
        continue
    elif (S[i] == '1' and T[i] == 'l') or (S[i] == 'l' and T[i] == '1'):
        continue
    elif (S[i] == '0' and T[i] == 'o') or (S[i] == 'o' and T[i] == '0'):
        continue
    else:
        ans = 'No'
        break

print(ans)

B問題

ポイント

ある番号の人に対して隣り合って写真を撮ったことのある人の番号をsetで記録
setの差集合を1~Nの全体集合からとることで、隣合わなかった人の番号を特定
隣り合わなかったペアについてset列で記録し、重複ペアが出ないようにする

自分の実装

ABC_303_B.py

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

lines = list(list(map(int ,input().split())) for i in range(M))

# 番号i の人間が隣に並んだ人の番号をカウント
neighbor_num = [set([i]) for i in range(N+1)]

for line in lines:
    for i in range(N):
        if i == 0:
            neighbor_num[line[i]].add(line[i+1])
        elif i == N-1:
            neighbor_num[line[i]].add(line[i-1])
        else:
            neighbor_num[line[i]].add(line[i+1])
            neighbor_num[line[i]].add(line[i-1])
            
not_good_relation_list = set()
num_list = set([i+1 for i in range(N)])

for i in range(1, N+1):
    not_good_relation_with_i = num_list - neighbor_num[i]    
    couple = set()
    not_good_relation_with_i = list(not_good_relation_with_i)
    for j in range(len(not_good_relation_with_i)):
        couple |= set([str(min(not_good_relation_with_i[j], i)) + str(max(not_good_relation_with_i[j], i))])
    not_good_relation_list |= couple

print(len(not_good_relation_list))

C問題

ポイント

回復アイテムの座標をsetで保存しておくことで座標検索の計算量を削減する

自分の実装

ABC_303_C.py

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

def can_complete_moves(N, M, H, K, S, items):
    x, y = 0, 0  # 高橋くんの座標
    item_positions = set(items)  # アイテムの座標を集合として管理
    
    for i in range(N):
        # 移動先の座標を計算
        if S[i] == 'R':
            x += 1
        elif S[i] == 'L':
            x -= 1
        elif S[i] == 'U':
            y += 1
        elif S[i] == 'D':
            y -= 1
        
        H -= 1  # 体力を消費
        
        if H < 0:
            return False  # 体力が負になった場合、移動を中止
        
        # 移動先にアイテムがあり、かつ体力がK未満の場合
        if (x, y) in item_positions and H < K:
            item_positions.remove((x, y))  # アイテムを使用
            H = K  # 体力をKに回復
    
    return True

S = input()
items = [tuple(map(int, input().split())) for _ in range(M)]

result = can_complete_moves(N, M, H, K, S, items)
if result:
    print("Yes")
else:
    print("No")

D問題

ポイント

CapsLock が　ON, OFF の状態で次の文字を打つという状況に関して2次元DPによって最小時間となるように場合分けする
ON -> ON, ON -> OFF, OFF -> OFF, OFF -> ONとなるパターンについて遷移先の状況を考慮しながら最小となる時間で足していく

自分の実装

ABC_303_D.py

from collections import deque

X, Y, Z = map(int, input().split())

S = deque(list(input()))

# 文字列Sの文字数
length =len(S)

# dp[i][0], dp[i][1]: CapsLockが OFF, ON 状態
dp = [[0]*2 for _ in range(length+1)]

# OFF -> OFF, OFF -> ON, ON -> ON, ON -> OFF で a, A を打つ時間
time = [[X, Y], [Z+Y, Z+X], [Y, X], [Z+X, Z+Y]]
for i in range(1, length+1):
    S_i = S.popleft()
    # 次の文字を打つためにかかる時間
    # a
    if S_i == 'a':
        time_consumed = [time[0][0], time[1][0], time[2][0], time[3][0]]
    # A
    else:
        time_consumed = [time[0][1], time[1][1], time[2][1], time[3][1]]
    if i != 1:
        dp[i][0] = min(dp[i-1][0]+time_consumed[0], dp[i-1][1]+time_consumed[3])
        dp[i][1] = min(dp[i-1][0]+time_consumed[1], dp[i-1][1]+time_consumed[2])
    else:
        dp[i][0] = dp[i-1][0]+time_consumed[0]
        dp[i][1] = dp[i-1][0]+time_consumed[1]

print(min(dp[-1]))

感想

　今回はC問題まで時間内で解けた。D問題はコンテストが終わって少ししてからACできた。D問題でDPを使って解くということには、コンテスト時間内で気付けてはいたものの、実装が間に合わなかった。また、C問題に関しても、回復アイテムの位置の検索にsetを用いることに気づくのに3ペナも食らってからようやく気付けたのでかなり時間をロスしてしまった。