ABC289 回想・解説(Python)

Thumbnail

目次

前提

AtCoder Biginner Contest289のPythonの解答コードです。

A - flip

問題文通りに実装する。一旦別の文字に退避させておいて、変換する。

A - flip

S = input()
S = S.replace("0", "2")
S = S.replace("1", "0")
S = S.replace("2", "1")
print(S)

解説を見るとstr.translate関数を使うと一発で実装できるらしい。

A - flip

print(input().translate(str.maketrans({'0': '1', '1': '0'})))

translate関数には__getitem__() によるインデックス指定を実装するオブジェクトである必要があるが、str.maketransで簡単に変換用のオブジェクトを生成できる。https://docs.python.org/ja/3/library/stdtypes.html#str.translate

B - レ

漢文のレ点を思い出して解く。問題文は特に読まず、漢文の読む順番を答えるんだろうなぁというあたりをつけて、入出力の例を見て確信にかえる。

前から一文字ずつ読んでいき、レ点がついていたら、tmpの先頭に追加していく。レ点がついていなければ、tmpの先頭に追加して、tmpをansにくっつける。

最後まで同様の処理を行なって、出力する。

B - レ

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

ans = []
tmp = []
for i in range(1, N + 1):
    if i not in A:
        tmp.insert(0, i)
        ans += tmp
        tmp = []
    else:
        tmp.insert(0, i)
print(*ans)

C - Coverage

Mが小さいので、bit全探索して全ての方法を試しても間に合うことがわかる。

完全な集合compを用意してあげて、bit全探索で選んだ集合と一致するならカウントアップ。

C - Coverage

N, M = map(int, input().split())
A = []
for i in range(M):
    c = int(input())
    a = set(map(int, input().split()))
    A.append(a)

comp = set(range(1, N + 1))
cnt = 0
for i in range(1, 1 << M):
    tmp = set()
    for j in range(M):
        if (i >> j) & 1:
            tmp |= A[j]
    if tmp == comp:
        cnt += 1
print(cnt)

D - Step Up Robot

DPだなと思う。その段数に登れるかどうかだけわかれば良いので、一次元のDPでいい。

D - Step Up Robot

N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))
X = int(input())
trap = [False] * (X + 1)
for b in B:
    trap[b] = True

dp = [False] * (X + 1)
dp[0] = True
for i in range(1, X + 1):
    for a in A:
        if i - a >= 0 and dp[i - a] and not trap[i]:
            dp[i] = True
            break

print("Yes" if dp[X] else "No")