ABC 301 備忘録

概要

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

A問題

ポイント

• 互いの勝った数をカウント
• どちらかの勝った回数が総試合数の半分となった時に勝者を決定

自分の実装

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問題

ポイント

• 数列Aを先頭からdequeで見ていき、直前と現在見ている数字の情報を保持
• 直前の数字との大小比較を行い、操作2の処理を実行

自分の実装

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問題

ポイント

• 各アルファベットの個数を文字列ごとにnumpyで保存
• @の個数は各文字列ごとに個数を数える
• アルファベットとnumpyのインデックスはascii文字変換により対応させる
• S,T の numpy 行列の引き算を行い、各アルファベットの個数差の絶対値を計算
• a,t,c,o,d,e,r 以外の文字に関して、個数差の絶対値が0以上である場合はNo
• 上記の条件を満たしている場合は、変換できる７つのアルファベットに関して@の個数を超えない個数であるかどうかを比較

自分の実装

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問題

ポイント

• Sの?をすべて0に変えてもNよりも大きい場合は-1
• そうでない場合には0とした桁に対して1とした場合にNを超えないならば1に変更

自分の実装

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に変更」を上の桁から実行するという考えが浮かばなかった。