AtCoder Beginner Contest 455 参加記録と解答例 (A~D問題)

本記事は、AtCoder Beginner Contest 455 (ABC455) に参加した際の、A〜D問題の復習と解答の備忘録です。コンテスト中に考えた解法の方針や、提出したPythonのコードについて整理しています。

A - 455

配点 : 100 点

問題文

整数 A,B,C が与えられます。 $A \neq B$ かつ $B=C$ であるならば Yes を、そうでないならば No を出力してください。

制約

• 1≤A,B,C≤9
• 入力される値はすべて整数

自分の解答の方針

そのまま $A \neq B$ かつ $B == C$ を判定。

提出したコード

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

---

B - Spiral Galaxy

配点 : 200 点

問題文

H 行 W 列のグリッドがあります。各マスは白 (.) または黒 (#) で塗られています。
グリッドの長方形領域であって、点対称に塗られているものの個数を求めてください。

制約

• 1≤H,W≤10
• H,W は整数
• $S_i$ は ., # からなる長さ W の文字列

自分の解答の方針

H, W が小さいので、すべての長方形領域 $(h_1, w_1, h_2, w_2)$ について、領域内のすべてのマスを走査して点対称か判定する。

提出したコード

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
count = 0
for h1 in range(H):
    for h2 in range(h1,H):
        for w1 in range(W):
            for w2 in range(w1,W):
                flag = True
                for i in range(h1,h2+1):
                    if not flag:
                        break
                    for j in range(w1,w2+1):
                        if S[i][j] != S[h1+h2-i][w1+w2-j]:
                            flag = False
                if flag:
                    count += 1
print(count)

---

C - Vanish

配点 : 300 点

問題文

整数列 $A=(A_1, A_2, \dots, A_N)$ が与えられます。
「整数 $x$ を選び、$A_i = x$ なる各 $i$ について $A_i$ の値を 0 に置き換える」という操作をちょうど K 回行った後の A の各要素の和として考えられる最小値を求めてください。

制約

• 1≤K≤N≤3×$10^5$
• 1≤$A_i$≤$10^9$
• 入力される値はすべて整数

自分の解答の方針

同じ数字の出現回数をカウントし、「数値 × 出現回数」のリストを作成してソートする。
大きいほうからK個取り除いたものの和が答えになる

提出したコード

N,K = map(int,input().split())
A = list(map(int,input().split()))
dict = dict()
for i in A:
    if i in dict:
        dict[i] += 1
    else:
        dict[i] = 1
list = []
for key, value in dict.items():
    list.append(key*value)
list.sort()
# print(list)
if len(list) <= K:
    print(0)
else:
    print(sum(list[:len(list)-K]))

---

D - Card Pile Query

配点 : 400 点

問題文

N 枚のカードと N 個の山があります。はじめ山 $i$ にはカード $i$ のみが積まれています。
「カード $C_i$ 以上の束を、カード $P_i$ （山の一番上）の上に移動させる」というクエリに Q 回答えた後、各山のカードの枚数を出力してください。

制約

• 1≤N,Q≤3×$10^5$
• 操作の直前、カード $P_i$ は必ず山の一番上にある。

自分の解答の方針

指定されたカードがどの山に属するか、カードの山の一番下のカード、あるカードの下にいるカード、あるカードの上にいるカードをそれぞれ保持しておき、各クエリでそれらを更新する。
最終的にそれぞれの山の一番下からカードをたどっていきカウントすることで答えを得る。

提出したコード

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

# そのカードが現在どの山に所属しているか
current_place = dict()
for i in range(1,N+1):
    current_place[i] = i

# カードの山の一番下のカード
mountain_roots = [i for i in range(N+1)]

# 自分の上にいるカード
on_card = [None for _ in range(N+1)]

# 自分の下にいるカード
under_card = [None for _ in range(N+1)]

for _ in range(Q):
    C,P = map(int,input().split())
    if mountain_roots[current_place[C]] == C:
        mountain_roots[current_place[C]] = None
    else:
        on_card[under_card[C]] = None
    on_card[P] = C
    under_card[C] = P

ans = []
for i in range(1,N+1):
    if mountain_roots[i] == None:
        ans.append("0")
    else:
        count = 1
        current_card = mountain_roots[i]
        while on_card[current_card]:
            current_card = on_card[current_card]
            count += 1
        ans.append(str(count))
print(" ".join(ans))