ABC455をPythonで（A～E）

Ｓｋｙ株式会社プログラミングコンテスト2026（AtCoder Beginner Contest 455）の解答等の速報的まとめ

A問題

そのまま

A

a, b, c = map(int, input().split())
print("Yes" if a != b == c else "No")

B問題

全通り調べる

B

h, w = map(int, input().split())
s = [input() for _ in range(h)]

def check(h1, h2, w1, w2):
    for i in range(h2 - h1 + 1):
        for j in range(w2 - w1 + 1):
            if s[h1 + i][w1 + j] != s[h2 - i][w2 - j]:
                return False
    return True


ans = 0
for i in range(h):
    for j in range(i, h):
        for k in range(w):
            for l in range(k, w):
                if check(i, j, k, l):
                    ans += 1

print(ans)

C問題

消したときに総和から減る値を全種類求める
上から$k$個を除外して合計する

C

n, k = map(int, input().split())
a = sorted(map(int, input().split()))

d = dict()
for a_i in a:
    if a_i not in d:
        d[a_i] = 0
    d[a_i] += 1

lst = list()
for key, val in d.items():
    lst.append(key * val)

lst.sort()
if len(lst) <= k:
    print(0)
else:
    print(sum(lst[:-k]))

D問題

各カードの上にあるカード（コードのchild）と下にあるカード（コードのparent）を設定する
カードを移動させるたびに適切にパラメータを変更する

最後の計算はparent == -1となるカードは移動していないのでそこから連鎖的に計算する

D

class Card:
    parent = -1
    child = -1

n, q = map(int, input().split())

card = [Card() for _ in range(n)]

for _ in range(q):
    c, p = map(lambda x:int(x) - 1, input().split())
    if card[c].parent != -1:
        par = card[c].parent
        card[par].child = -1
        card[c].parent = -1

    card[c].parent = p
    card[p].child = c

ans = list()
for i in range(n):
    if card[i].parent != -1:
        ans.append(0)
    else:
        ans_i = 0
        now = i
        while now >= 0:
            ans_i += 1
            now = card[now].child
        ans.append(ans_i)

print(*ans)

E問題

部分文字列で出現回数が一致するパターンの計算は簡単にできるので、そこから答えを導出する

$(A,B)$を出現回数が一致するパターン数とすると

$答え = 総パターン数 - (A,B) - (B,C) - (C,A) + (A,B,C)*2$

※ $ (A,B) \supseteq (A,B,C)$なので$(A,B,C)$は3回引いている

E

def make_diff(a, b):
    res = [0]
    for s_i in s:
        if s_i == a:
            res.append(res[-1] + 1)
        elif s_i == b:
            res.append(res[-1] - 1)
        else:
            res.append(res[-1])
    return res


def count_two(lst):
    d = dict()
    res = 0
    for l_i in lst:
        if l_i not in d:
            d[l_i] = 0
        res += d[l_i]
        d[l_i] += 1
    return res


n = int(input())
s = input()

diff_ab = make_diff("A", "B")
diff_bc = make_diff("B", "C")
diff_ca = make_diff("C", "A")

same_ab = count_two(diff_ab)
same_bc = count_two(diff_bc)
same_ca = count_two(diff_ca)

same_abc = 0
d = dict()
for ab_i, bc_i in zip(diff_ab, diff_bc):
    key = (ab_i, bc_i)
    if key not in d:
        d[key] = 0
    same_abc += d[key]
    d[key] += 1

print(n * (n + 1) // 2 - same_ab - same_bc - same_ca + same_abc * 2)