AtCoder ABC372 振り返り感想戦(ほぼ緑コーダーがPythonでA〜D問題まで)

ABC372 感想まとめ

ユニークビジョンプログラミングコンテスト2024 秋（AtCoder Beginner Contest 372） - AtCoder

今回は久々にRated参加で、C問題まで3問解答(1ペナ)でした。パフォーマンス 774 で、レーティングは 776 → 775(-1) でした。

C問題までは比較的早く解けたのですが、その後の70分はD問題で詰まってしまい...。D問題は終了10分前に優先度つきキュー(heapq)を使う解法を思いつき、なんとか提出までは出来たのですが、残念ながらテストケース1つだけWAで通らずでした。

コンテスト終了4分後にD問題を通せたので、もう少し解法に気付いれいれば...。惜しい。

A - delete .

配列 answers に "." 以外の文字を貯めていき、最後に配列を文字列に変換しています。

S = input()

answers = []
for i in range(len(S)):
    if S[i] != ".":
        answers.append(S[i])
print("".join(answers))

B - 3^A

与えられたMに対して、3^10が引けるか？, 3^9が引けるか？....3^0が引けるか？を順番に調べていく。

要するにMを3進法で表現するとどうなるかという問題ですね。

M = int(input())
answers = []

m = M
while m > 0:
    # Mから3 ** aが引ければ、answersに追加
    for a in range(10, -1, -1):
        temp = 3 ** a
        if temp <= m:
            m = m - temp
            answers.append(a)
            break
print(len(answers))
print(*answers)

C - Count ABC Again

最初に"ABC"の数をカウントしておく(変数countに入れておく)。

その後、クエリーが来るたびに以下を数えて、countに足したり引いたりする。

• 文字置換前の"ABC"の数
• 文字置換後の"ABC"の数

---

Pythonの場合、Sを文字列ではなく配列として使うのがポイント。クエリーの処理のときに、1文字だけを変更するのだが、これが文字列で処理すると遅くなるため。

私はこれで1ペナになりました。。。

# X文字目をCに変更(この処理は遅いので、何回もやるとTLEになってしまう)
S = input()
S = S[:X] + C + S[X+1:] 

# X文字目をCに変更(配列バージョン。これは速い)
S = list(input())
S[X] = C

回答例

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

# 初期状態のABCの数を数える
count = 0
for i in range(N-2):
    if S[i] == "A" and S[i+1] == "B" and S[i+2] == "C":
        count += 1

for _ in range(Q):
    X, C = input().split()
    X = int(X)
    X -= 1

    # 変更前の数を数える
    before = 0
    if X+2 < N and S[X] == "A" and S[X+1] == "B" and S[X+2] == "C":
        before += 1
    if X-1 >= 0 and X+1 < N and S[X-1] == "A" and S[X] == "B" and S[X+1] == "C":
        before += 1
    if X-2 >= 0 and S[X-2] == "A" and S[X-1] == "B" and S[X] == "C":
        before += 1

    # X文字目をCに変更
    S[X] = C

    # 変更後の数を数える
    after = 0
    if X+2 < N and S[X] == "A" and S[X+1] == "B" and S[X+2] == "C":
        after += 1
    if X-1 >= 0 and X+1 < N and S[X-1] == "A" and S[X] == "B" and S[X+1] == "C":
        after += 1
    if X-2 >= 0 and S[X-2] == "A" and S[X-1] == "B" and S[X] == "C":
        after += 1

    count += after - before
    print(count)

D - Buildings

コンテスト本番の時間内では解けなかった問題。最初は最大値が更新された箇所の累積和？で使って解くのかなとか考えていた。ただこの方法は、入力例3のときに答えが合わなくて失敗。

優先度つきキュー(heapq)を使って、ビル群Hを後ろから探索していく方法をなかなか思いつかなくて、時間内では解けなかった。終了4分後に正解を提出できたので、もう少しでした...。

N = int(input())
H = list(map(int, input().split()))

heapqList = []
heapq.heapify(heapqList)

answer = []
answer.append(0) # 最後は必ず0になる

# 配列Hを後ろから探索
for i in range(N-1, 0, -1):
    current = H[i]
    heapq.heappush(heapqList, current)

    # キューの中から、今の高さcurrentより低いものを除外していく（=currentより高いビルの数）
    while heapqList[0] < current:
        heapq.heappop(heapqList)
    answer.append(len(heapqList))

# 反転して出力
answer = answer[::-1]
print(*answer)