ABC 303 備忘録

## 概要
　今回はABC303（2023年5月27日21:00~22:40）について実装上のポイントと自分の実装についてコメントしていきたいと思う。
## A問題
https://atcoder.jp/contests/abc303/tasks/abc303_a

### ポイント
- 3つの条件について、一度でもいずれかを満たさない場合は`No`となるようにする
- `ans = 'Yes'`としておき、条件分岐で変化させる
### 自分の実装
```Python: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問題
https://atcoder.jp/contests/abc303/tasks/abc303_b

### ポイント
- ある番号の人に対して隣り合って写真を撮ったことのある人の番号を`set`で記録
- `set`の差集合を`1~N`の全体集合からとることで、隣合わなかった人の番号を特定
- 隣り合わなかったペアについて`set`列で記録し、重複ペアが出ないようにする
### 自分の実装
```Python: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問題
https://atcoder.jp/contests/abc303/tasks/abc303_c

### ポイント
- 回復アイテムの座標を`set`で保存しておくことで座標検索の計算量を削減する
### 自分の実装
```Python: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問題
https://atcoder.jp/contests/abc303/tasks/abc303_d

### ポイント
- CapsLock が　`ON, OFF` の状態で次の文字を打つという状況に関して2次元DPによって最小時間となるように場合分けする
- `ON -> ON, ON -> OFF, OFF -> OFF, OFF -> ON`となるパターンについて遷移先の状況を考慮しながら最小となる時間で足していく
### 自分の実装
```Python: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ペナも食らってからようやく気付けたのでかなり時間をロスしてしまった。