ABC455 (Ｓｋｙ株式会社プログラミングコンテスト2026)参加録

最近時間があるときはまたABCにひっそり参加するようになりました。
A-Dまではすんなり15分くらいで通したものの、Eの包除原理をちゃんと考えられずそのまま終了。
AtCoder ProblemsのD埋めではなくE埋めに移行した方がいいかもなーと思ってきたこの頃。

A: 455

素直にA != B && B == Cを判定した。

def solve():
    input = sys.stdin.readline 
    A, B, C = map(int, input().split())
    if A != B and B == C:
        print("Yes")
    else:
        print("No")


    return 0

B: Spiral Galaxy

H, Wが小さいので力技で全h, wの組全マスの判定をかけた。

def solve():
    input = sys.stdin.readline 
    H, W = map(int, input().split())
    S = [input().strip("\n") for _ in range(H)]
    ans = 0
    for h1 in range(H):
        for h2 in range(h1, H):
            for w1 in range(W):
                for w2 in range(w1, W):
                    canCount = True
                    for i in range(h1, h2+1):
                        for j in range(w1, w2+1):
                            if S[i][j] != S[h1+h2-i][w1+w2-j]:
                                canCount = False
                    ans += 1 if canCount else 0
    print(ans)

    return 0

C: Vanish

それぞれの数字を辞書で管理し、合計を保持しておく。
合計値の上位K個を0にして総和をとる。

def solve():
    input = sys.stdin.readline 
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    AD = dict()
    for a in A:
        if a not in AD:
            AD[a] = 0
        AD[a] += a
    sums = []
    for key, value in AD.items():
        sums.append(value)
    sums.sort(reverse=True)
    for i in range(min(K, len(sums))):
        sums[i] = 0
    print(sum(sums))

    return 0

D: Card Pile Query

カードCiをPiの上に移動する際に、Ciの上に何が乗っているかは関係がない。
各操作でCiの下に何が来るか(Piの上に何が来るか)を保持しておき、全操作が終わった終わった後に、動かされていないカードから順に上にあるカードをたどっていけば枚数が分かる。

def solve():
    input = sys.stdin.readline 
    N, Q = map(int, input().split())
    B = [-1] * N
    for i in range(Q):
        c, p = map(int, input().split())
        B[c-1] = p-1
    T =[-1] * N
    Start = []
    for i, b in enumerate(B):
        if b == -1:
            Start.append(i)
        else:
            T[b] = i
    Count = [0] * N
    for s in Start:
        idx = s
        ci = s
        Count[idx] += 1
        while T[ci] > -1:
            ci = T[ci]
            Count[idx] += 1
    print(*Count)

    return 0

E: Unbalanced ABC Substrings

AとBの差、AとCの差、BとCの差をキーとして、今見ているindexより左にそれぞれ何回発生したかを保持しておく。　　 A == B, B == C, C == Aの数をカウントしておいて、全組み合わせ数から引けば求まる...という方針までは良かったけど、包除を考えて重複を取り除くところをちゃんと考えられず通せず...

def solve():
    input = sys.stdin.readline 
    N = int(input())
    S = input().strip("\n")
    AB = [0] * (N+1)
    AC = [0] * (N + 1)
    BC = [0] * (N + 1)
    bd = {0 : 1}
    cd = {0 : 1}
    bcd = {0 : 1}
    dup = {(0, 0): 1}

    double = 0
    for i in range(N):
        s = S[i]
        if s == "A":
            AB[i+1] = AB[i] + 1
            AC[i+1] = AC[i] + 1
            BC[i+1] = BC[i]
        elif s == "B":
            AB[i+1] = AB[i] - 1
            AC[i+1] = AC[i]
            BC[i+1] = BC[i] + 1
        else:
            AB[i+1] = AB[i]
            AC[i+1] = AC[i] - 1
            BC[i+1] = BC[i] - 1
        
        b = AB[i+1]
        c = AC[i+1]
        bc = BC[i+1]
        if b not in bd: bd[b] = 0
        if c not in cd: cd[c] = 0
        if bc not in bcd: bcd[bc] = 0
        if (b, c) not in dup: dup[(b, c)] = 0
        double += bd[b] + cd[c] + bcd[bc] - 2 * dup[(b, c)]

        bd[b] += 1
        cd[c] += 1
        bcd[bc] += 1
        dup[(b, c)] += 1

    total = N * (N + 1) // 2
    print(total - double)

    return 0