ABC452をPythonで（A～D）

AtCoder Beginner Contest 452の解答等の速報的まとめ

A問題

条件をセットに入れて判定

A

gothec = {(1, 7), (3, 3), (5, 5), (7, 7), (9, 9)}

m, d = map(int, input().split())
print("Yes" if (m, d) in gothec else "No")

B問題

そのまま

B

h, w = map(int, input().split())
for i in range(h):
    for j in range(w):
        if i in [0, h - 1] or j in [0, w - 1]:
            print("#", end = "")
        else:
            print(".", end = "")
    print()

c問題

事前に文字の存在を整理しておいて
各文字ごとに作成できるか判定する

C

n = int(input())
fish = [list(map(int, input().split())) for _ in range(n)]
m = int(input())
s = [input() for _ in range(m)]

# [文字の長さ][i文字目]にある文字セット
s_dict = [[set() for _ in range(11)] for _ in range(11)]
for s_i in s:
    l = len(s_i)
    for j, s_j in enumerate(s_i, 1):
        s_dict[l][j].add(s_j)

def check(s):
    if len(s) != n:
        return False
    for i, s_i in enumerate(s):
        a_i, b_i = fish[i]
        if s_i not in s_dict[a_i][b_i]:
            return False

    return True

for s_i in s:
    print("Yes" if check(s_i) else "No")

D問題

$S_i$文字目以降で$T$が作成できるのは何文字目以降か順に判定していく
作成できるときは$i$からできるところの1文字前まで
できないときは$i$文字目以降すべてが対象

D

s = input()
t = input()

n = len(s)
# [sのi文字目][a~zがi文字目以降最初に出る場所]
lst = [[-1] * 26 for _ in range(n)]
for i in range(n - 1, -1, -1):
    for j in range(26):
        if i < n - 1:
            lst[i][j] = lst[i + 1][j]
    lst[i][ord(s[i]) - ord("a")] = i

ans = 0
for i in range(n):
    target = i
    cnt = 0
    for j, t_j in enumerate(t):
        if target >= n:
            break
        ind = lst[target][ord(t_j) - ord("a")]
        if ind == -1:
            break
        target = ind + 1
        cnt += 1

    if cnt == len(t):
        ans += target - 1 - i
    else:
        ans += n - i

print(ans)