ABC 301 備忘録

## 概要

　今回はABC 301（2023年5月13日21:00~22:40）のポイントと自分の実装について書いていこうと思う。

## A問題
https://atcoder.jp/contests/abc301/tasks/abc301_a
### ポイント
- 互いの勝った数をカウント
- どちらかの勝った回数が総試合数の半分となった時に勝者を決定
### 自分の実装
```Python:ABC_301_A.py
N = int(input())

S = list(input())

takahashi_win = 0
aoki_win = 0

for i in S:
    if i == "T":
        takahashi_win += 1
    elif i == "A":
        aoki_win += 1
    if takahashi_win == N // 2 and N %2 == 0:
        print("T")
        exit()
    elif aoki_win == N // 2 and N % 2 == 0:
        print("A")
        exit()

if takahashi_win > aoki_win:
    print("T")
else:
    print("A")

```

## B問題
https://atcoder.jp/contests/abc301/tasks/abc301_b
### ポイント
- 数列Aを先頭から`deque`で見ていき、直前と現在見ている数字の情報を保持
- 直前の数字との大小比較を行い、操作2の処理を実行
### 自分の実装
```Python:ABC_301_B.py
from collections import deque

N = int(input())

A = deque(list(map(int,input().split())))

new_A = deque()

last_num = A.popleft()
present_num = 0

for i in range(N-1):
    present_num = A.popleft()
    if abs(last_num - present_num) == 1:
        new_A.append(last_num)
        last_num = present_num
    elif last_num > present_num:
        for j in range(last_num, present_num, -1):
            new_A.append(j)
        last_num = present_num
    else:
        for j in range(last_num,present_num):
            new_A.append(j)
        last_num = present_num

new_A.append(present_num)

print(*new_A)
```

## C問題
https://atcoder.jp/contests/abc301/tasks/abc301_c
### ポイント
- 各アルファベットの個数を文字列ごとに`numpy`で保存
- `@`の個数は各文字列ごとに個数を数える
- アルファベットと`numpy`のインデックスは`ascii`文字変換により対応させる
- `S`,`T` の `numpy` 行列の引き算を行い、各アルファベットの個数差の絶対値を計算
- `a`,`t`,`c`,`o`,`d`,`e`,`r` 以外の文字に関して、個数差の絶対値が`0`以上である場合は`No`
- 上記の条件を満たしている場合は、変換できる７つのアルファベットに関して`@`の個数を超えない個数であるかどうかを比較
### 自分の実装
```Python:ABC_301_C.py
from collections import deque
import numpy as np

S = deque(list(input()))

T = deque(list(input()))

card_num = len(S)

S_letter = np.array([0 for i in range(26)])
T_letter = np.array([0 for i in range(26)])

S_at = 0
T_at = 0

for i in range(card_num):
    s_letter = S.popleft()
    t_letter = T.popleft()
    if s_letter == "@":
        S_at += 1
    else:
        S_letter[ord(s_letter)-97] += 1    
    if t_letter == "@":
        T_at += 1
    else:
        T_letter[ord(t_letter)-97] += 1

dif = abs(S_letter - T_letter)
dif_rev = S_letter - T_letter
atcoder = [dif_rev[0], dif_rev[2], dif_rev[3], dif_rev[4], dif_rev[14], dif_rev[17], dif_rev[19]]
S_change = 0
T_change = 0

for i in range(26):
    # 1 5 6 7 8 9 10 11 12 13 15 16 18 20 21 22 23 24 25
    # b f g h i j k  l  m  n  p  q  s  u  v  w  x  y  z
    if (dif[1] + dif[5] + dif[6] + dif[7] + dif[8] + dif[9] + dif[10] + dif[11] + dif[12] + dif[13] + dif[15] + dif[16] + dif[18] + dif[20] + dif[21] + dif[22] + dif[23] + dif[24] + dif[25]) != 0:
        print("No")
        exit()

for i in range(len(atcoder)):
    if atcoder[i] > 0:
        T_change += abs(atcoder[i])
    elif atcoder[i] < 0:
        S_change += abs(atcoder[i])

if T_change > T_at or S_change > S_at:
    print("No")
else:
    print("Yes")
```

## D問題
https://atcoder.jp/contests/abc301/tasks/abc301_d
### ポイント
- `S`の`?`をすべて`0`に変えても`N`よりも大きい場合は`-1`
- そうでない場合には`0`とした桁に対して`1`とした場合に`N`を超えないならば`1`に変更
### 自分の実装
```Python:ABC_301_D.py
S = list(reversed(input()))

N = int(input())

# 文字列Sのバイナリ変換の値
s = 0

# 文字列Sの中で`1`であるものだけバイナリ変換の値として加算
for i in range(len(S)):
    s |= (S[i] == "1") << i
# 表せる最小の値を超えてしまっている場合は-1
if s > N:
    print(-1)
# そうでない場合は、小さな桁から'?'を1に変換し、Nとの大小を比較
else:
    for i in reversed(range(len(S))):
        if S[i] == "?" and (s | 1 << i) <= N:
            s |= 1 << i
    print(s)    
```

## 感想
　今回はC問題まではスラスラできた気がする。D問題に関しては、本記事で書いたような実装はコンテスト中にはできなかった。特に、「そうでない場合には`0`とした桁に対して`1`とした場合に`N`を超えないならば`1`に変更」を上の桁から実行するという考えが浮かばなかった。