【AtCoder】ABC402をPythonで解く

1. はじめに

目的

ABCを解くことにより、とにかくRatingを上げていく。

注意点

言語はPython(PyPy 3.10-v7.3.12) を使用しています。

コンテスト情報

コンテスト名

AtCoder Beginner Contest 402

コンテストURL

https://atcoder.jp/contests/abc402

開催日

2025-04-19(土) 21:00 ~ 2025-04-19(土) 22:40 (100分)

配点

問題	点数
A	100
B	200
C	300
D	400
E	450
F	525
G	650

結果

順位：9129/10236

	総合	A	B	C	D	E	F	G
得点	300	100	200	(1)
時間	48:05	23:21	48:05

2. 問題と解法

A: CBC

コード

s = str(input())

app_letter = [i for i in s if i.isupper()]
print("".join(app_letter))

解法

1. 文字列$S$に対して、各文字が大文字かどうかを順に判断した。
2. $isupper$メソッドを使って、大文字と判別された文字を順番にリスト$app\_letter$に格納していった。
3. $join$メソッドを使って、リスト内の文字を結合し、一つの文字列として出力した。

改善点

+ ans = ""

わざわざリストを用意する必要もなく、空の文字列を用意するだけでよかった。

B: Restaurant Queue

コード

q = int(input())
order = []
query = [input().split() for _ in range(q)]
j = 0
for i in range(q):
  if len(query[i]) == 1:
    print(order[j])
    j += 1
  elif len(query[i]) == 2:
    a = int(query[i][0])
    order.append(int(query[i][1]))

解法

1. リスト$query$にすべてのクエリをリストの形で格納した。
2. リスト$query$は$list\ of\ list$になっており、外側のリストのインデックスは、クエリを処理する順番に対応している。
3. 各クエリは$2$つの要素からなり、$0$番目の要素が操作の種類、$1$番目の要素が対象の食券番号に対応している。（種類$2$のクエリには$1$番目の要素がない）
4. 処理すべきクエリの数は$Q$個なので、$Q$回のループで全てのクエリを処理できる。
5. クエリの種類が$1$であれば、リスト$order$に食券番号を追加し、種類が$2$であれば$order$の中から条件に従って出力を行う。

改善点

- query = [input().split() for _ in range(q)]
+ for _ in range(q):
+   query = list(map(int, input().split()))

そもそも各クエリはループ処理1回ごとに値を受け取るだけでいい。

from collections import deque

q = int(input())
query = deque()

for _ in range(q):
    t, *x = map(int,input().split())
    if t == 1:
        query.append(x[0])
    else:
        print(que[0])
        query.popleft()

この問題では、先入れ先だしFIFOのデータ構造をとる。
これをpythonで実行するには、collectionsライブラリのdequeを使うと容易に実装できる。

3. 解けなかった問題

C: Dislike Foods

コード

N, M = map(int, input().split())
disliked_count = [0] * M
ingredient_to_dishes = [[] for _ in range(N)]

for i in range(M):
  data = list(map(int, input().split()))
  K = data[0]
  ingredients = data[1:]
  disliked_count[i] = K

  for ing in ingredients:
    ingredient_to_dishes[ing - 1].append(i)

B = list(map(int, input().split()))
ans = 0
res = []

for b in B:
  b -= 1

  for dish in ingredient_to_dishes[b]:
    disliked_count[dish] -= 1
    if disliked_count[dish] == 0:
      ans += 1
  res.append(ans)

for r in res:
    print(r)

解法