ABC294 A-D問題の解説（Python）

はじめに

AtCoder Beginner Contest（略称：ABC）とは、AtCoderが週末に開催している、競技プログラミングコンテストのことです。

A-D問題について、自身の復習も兼ねて説明できればと思います。誤った記述やより良い解法などあれば、コメントをいただけると幸いです。

ABC294

A – Filter

問題

A問題

解説

Aの要素についてfor文を用いて偶数だけを取り出し、新しい配列に格納することで解くことができます。

下のコードはリスト内包表記を利用しています。filter関数を利用して解くこともできます。そのあたりはお好みで。

コード

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

# Aから偶数だけを取り出したリストを作成（リスト内包表記）
ans = [num for num in A if num % 2 == 0]
print(*ans)

B – ASCII Art

問題

B問題

解説

各マスの数字を文字に変換するために、リスト[“.”, “A”, “B”, ……, “Z”]を事前に作成します。リストの0番目は”.”、リストの1番目は”A”となり、今回行いたい変換と同じ対応になります。

あとは2重for文（行の繰り返しと行内のマスの繰り返し）を用いて実際に変換することで解くことができます。私はこの問題でも、A問題同様にリスト内包表記を用いました。

コード

from sys import stdin
import string
H, W = map(int, input().split())
l = [list(map(int, stdin.readline().split())) for _ in range(H)]

# リスト[".", "A", "B", ……, "Z"]を作成
charList = "." + string.ascii_uppercase

for row in l:
    # 行の数字を文字に変換したリストを作成
    ans = [charList[i] for i in row]
    print(*ans, sep="")

C – Merge Sequences

問題

C問題

解説

リストAとリストBをマージしたリストCについて、要素とインデックス（番号）を対応させた辞書を事前に作成しておくことで解くことができます。

コード

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

C = sorted(A + B)
# 要素とインデックス（番号）を対応させた辞書を作成
D = {num: i + 1 for i, num in enumerate(C)}

index_A = [D[a] for a in A]
index_B = [D[b] for b in B]

print(*index_A)
print(*index_B)

D – Bank

問題

D問題

解説

私はHeapDictを活用して解きました。HeapDictはheapqとdictを合わせたようなデータ構造です。HeapDictを使えば、O(logn)で要素の挿入と削除ができ、O(1)で要素の存在確認と最大値・最小値の取得ができます。詳しくは以下の記事をご参照ください。

【参考】Pythonでmultisetの代用ができるデータ構造（外部記事）

要素の挿入/削除/最小値最大値取得を繰り返し行う際はHeapDictを考えよう

受付に呼ばれていない人を管理する用と、受付に呼ばれたが受付に行っていない人を管理する用で、二つHeapDictを作成しました。それらを活用することで問題を解くことができます。

この問題は皆さん、色んな解き方をしたのではないかと思います。

コード

from sys import stdin
import heapq

# HeapDictクラス
class HeapDict:
    def __init__(self):
        self.h1 = [] # 最小値用
        self.h2 = [] # 最大値用（本問では不要）
        self.d = dict()

    def insert(self,x):
        heapq.heappush(self.h1,x)
        heapq.heappush(self.h2,-x)
        if x not in self.d:
            self.d[x] = 1
        else:
            self.d[x] += 1

    def erase(self,x):
        if x not in self.d or self.d[x] == 0:
            print(x,"is not in HeapDict")
            exit()
        else:
            self.d[x] -= 1

        while len(self.h1) != 0:
            if self.d[self.h1[0]] == 0:
                heapq.heappop(self.h1)
            else:
                break

        while len(self.h2) != 0:
            if self.d[-self.h2[0]] == 0:
                heapq.heappop(self.h2)
            else:
                break

    def is_exist(self,x):
        if x in self.d and self.d[x] != 0:
            return True
        else:
            return False

    def get_min(self):
        return self.h1[0]

    def get_max(self):
        return -self.h2[0]

N, Q = map(int, input().split())
l = [list(map(int, stdin.readline().split())) for _ in range(Q)]

hd1 = HeapDict() # 受付に呼ばれていない人の管理
for i in range(N):
    hd1.insert(i + 1)
hd2 = HeapDict() # 受付に呼ばれたが受付に行っていない人を管理

for event in l:
    if event[0] == 1:
        min = hd1.get_min()
        hd1.erase(min)
        hd2.insert(min)
    elif event[0] == 2:
        hd2.erase(event[1])
    else:
        print(hd2.get_min())