[ABC294 Python]AtCoder Beginner Contest 294A～D問題Python解説

前々回からスクリプトにコメントアウトで解説文を挿入しています。
前より見にくい等ありましたらご連絡いただけると幸いです。

A問題

https://atcoder.jp/contests/abc294/tasks/abc294_a

# 入力
N = int(input())
A = list(map(int, input().split()))
# リストAの全ての要素について
for i in A:
    # 2で割り切れれば出力する
    if i%2 == 0:
        # 改行なしで出力する方法
        print(i, end=" ")

偶数=2で割ると余りが0である数となります。
余りは％で求めることができるので、
リストAを順番に見ていって出力しましょう。

B問題

https://atcoder.jp/contests/abc294/tasks/abc294_b

# 入力
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
# 文字列Sを用意
# Sはピリオドか大文字アルファベットになるので、最初は全てピリオドに設定しておく
S = [["." for _ in range(W)] for __ in range(H)]
# 大文字アルファベット
alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
# 行列Aを1要素ずつ見ていく
for i in range(H):
    for j in range(W):
        # Aijが0ならばもともとピリオドにしているためスルー
        if A[i][j] == 0:
            continue
        # そうでなければAij番目の大文字アルファベット
        else:
            S[i][j] = alphabet[A[i][j]-1]
# Siを文字列型で出力
for i in range(H):
    print("".join(S[i]))

最初に入力したAとは別に出力用のSを用意しましょう。
Sは初期値をピリオドにして置き、
Aijが0じゃないときに大文字アルファベットに置き換えます。

C問題

https://atcoder.jp/contests/abc294/tasks/abc294_c

# インポート
import bisect
# 入力
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
# 行列C
C = A + B
# 昇順にソートする
C.sort()
# Aが何番目にあるかあるかを表すリスト
ansA = []
for i in A:
    # 二分探索で何番目にあるかを求める
    a = bisect.bisect(C, i)
    ansA.append(a)

# Bが何番目にあるかあるかを表すリスト
ansB = []
for i in B:
    # 二分探索で何番目にあるかを求める
    b = bisect.bisect(C, i)
    ansB.append(b)
# それぞれを空白区切りで出力する
print(*ansB)
print(*ansB)

二分探索で何番目にあるかを求めていきましょう。
Pythonではbisectライブラリを使うと便利です。

Pythonで二分探索を行うライブラリ「bisect」 - Qiita

問題文通り、リストCをソートし、
AとBそれぞれについて、何番目にあるかを求めていきます。

D問題

https://atcoder.jp/contests/abc294/tasks/abc294_d

# 入力
N, Q = map(int, input().split())
# 最も小さい番号の人
minN = 1
# 既に呼ばれた人の集合
gone = set()
# イベントを順番に見ていく
for i in range(Q):
    # 入力
    e = list(map(int, input().split()))
    # イベントが1の場合何もすることがない
    if e[0] == 1:
        continue
    # イベントが3の場合
    elif e[0] == 3:
        while True:
            # 最も小さい番号の人が呼ばれていなかったら、
            # 番号を出力する
            if minN not in gone:
                print(minN)
                break
            # その人が呼ばれていたら次の人に行く
            else:
                minN += 1
    # イベントが2の場合、xをgoneに保存
    else:
        x = e[1]
        gone.add(x)

出力例1の解説のように
「受付に呼ばれたが受付に行っていない人の集合」
を保存していくとTLEになります。
保存するべき集合は、
「既に受付に行った人の集合」
です。

今回はN人が3パターンに分類できます。
①まだ、受付に呼ばれていない人
②受付に呼ばれたけど、まだ受付に行っていない人
③受付に行った人

ここで1つポイントとなるのが、
番号で言うと、②<①になるということです。
②を小さい順にみていくと①に行く前に答えを見つけることができます。
つまり、②の最小値minNだけ変数として保存しておけばいいということになります。