ABC 294 備忘録

概要

今回はABC294（2023年3月19日21:00 ~ 22:40）の参加記録について自分の実装と感想について記していこうと思う。

A問題

ポイント

• リストとして標準入力を受け取り、偶数のみを出力するリストとして保存
• 出力する際にリスト形式ではなく、空白区切りで1行で出力

自分の実装

ABC_294_A.py

N = int(input())

sequence_A = list(map(int,input().split()))

even_squences = []

for num in sequence_A:
    if num%2 == 0:
        even_squences.append(num)
        
print(*even_squences)

B問題

ポイント

• 複数行の数列の標準入力をリストとして保存
• 各数字に該当するアルファベットの配列を自作する or アスキー文字変換を用いて数字から大文字アルファベットへの変換を行う
• 変換したリストを保存しておき、最後に文字列として出力

自分の実装

ABC_294_B.py

H, W = map(int,input().split())

squences_A = list(list(map(int,input().split())) for i in range(H))

ans_squences_A = []

for ith_line in squences_A:
    ith_letter_line = ""
    for num in ith_line:
        if num!=0:
            ith_letter_line+=(chr(num+64))
        else:
            ith_letter_line+=(".")
    ans_squences_A.append(ith_letter_line)

for letter_lines in ans_squences_A:
    print(letter_lines)

C問題

ポイント

• 数列A,B を標準入力からリストに保存
• 数列A,B は狭義単調増加列であるため、キューで左側の数字から比較する
• 比較している数字のうち小さなものから次の数字に変換する
• 直前で変換した数字の出自がどちらの数列であったかを記録しておく
• いずれかの数列の数字が先に全て出力された場合に備えて各数列で出た数字の数を記録しておく

自分の実装

ABC_294_C.py

from collections import deque

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

sequences_A = deque(list(map(int,input().split())))
sequences_B = deque(list(map(int,input().split())))

order_A_in_C = deque()
order_B_in_C = deque()

count = 1
last_num = 0
A_num = 0
B_num = 0

len_count_A = 0
len_count_B = 0

while count <= N+M-1:
    if last_num == 0:
        A_num = sequences_A.popleft()
        B_num = sequences_B.popleft()
    elif last_num == 1 and len_count_A <= N-1:
        A_num = sequences_A.popleft()
    elif last_num == 2 and len_count_B <= M-1:
        B_num = sequences_B.popleft()
        
    if A_num < B_num and len_count_A<N:
        last_num = 1
        order_A_in_C.append(count)
        len_count_A+=1
    elif A_num > B_num and len_count_B<M:
        last_num = 2
        order_B_in_C.append(count)
        len_count_B+=1
    elif A_num < B_num:
        last_num = 2
        order_B_in_C.append(count)
        len_count_B+=1
    else:
        last_num = 1
        order_A_in_C.append(count)
        len_count_A+=1
    count+=1

if A_num > B_num:
    order_A_in_C.append(count)
else:
    order_B_in_C.append(count)

print(*order_A_in_C)        
print(*order_B_in_C)

D問題

ポイント

• 人の数 N と イベント数 Q を標準入力で受け取った後、Q個のイベントを処理
• 呼ばれていないと受付に人が行くイベントは起こらない
• 呼ばれる番号は小さな番号の人からなので、キューで計算量を節約
• 3つ目のイベントの処理で受付に呼ばれている人の確認が必要なので、setで保存しておく（番号の重複対策でも兼ねている）

自分の実装

ABC_294_D.py

from collections import deque

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

customer = deque(i+1 for i in range(N))
called = set()

for i in range(Q):
    event = list(map(int,input().split()))
    if event[0] == 1:
        called_customer = customer.popleft()
        called.add(called_customer)
    elif event[0] == 2:
        called.remove(event[1])
    else:
        recalled = deque(called).popleft()
        called = set(called)
        print(recalled)

感想

結果としては3完だった。C問題について思いのほか苦戦してしまった。D問題についても自分的には実装できたつもりであったが、TLEしてしまった。おそらく、set列の変換を毎回起こさないといけなかったのでそこで計算量が多くなってしまっていたのだろう。公式解説ではC++の解説が主なので、Pythonの解説が出てきたら再度挑戦してみようと思う。最近はコンテストの結果的に不調なので、隙間時間にC、D問題を埋めていこうと思う。