ABC324をPythonで（A~E）

日本レジストリサービス（JPRS）プログラミングコンテスト2023（AtCoder Beginner Contest 324）

A問題

setに入れて確認

A

input()
s = list(map(int, input().split()))
print("YNeos"[len(set(s))>1::2])

B問題

2と3で割れるだけ割る

B

n = int(input())
while n % 2 == 0:n //= 2
while n % 3 == 0:n //= 3
print("YNeos"[n>1::2])

C問題

各Sに対して調べる。
1文字差があるときは、1つ以外違うか確認
同じ文字数のときは、同じ場所の違う文字の数が1以下か調べる

C

n, t = input().split()

def check(s, t):
    if len(s) + 1 != len(t):return False
    i = 0
    while i < len(s) and s[i] == t[i]:
        i += 1
    while i < len(s) and s[i] == t[i + 1]:
        i += 1

    return i == len(s)

ans = []
for i in range(int(n)):
    s = input()
    if abs(len(s) - len(t)) == 1:
        if check(s, t) or check(t, s):
            ans.append(i + 1)
    elif len(s) == len(t):
        cnt = sum(s_i != t_i for s_i, t_i in zip(s, t))
        if cnt <= 1:
            ans.append(i + 1)

print(len(ans))
print(*ans)

D問題

10^13未満の平方数は10^7個未満なので
それぞれの平方数について、Sから作れるか調べる。

D

n = int(input())
S = input()
s = [0] * 10
for s_i in S:s[int(s_i)] += 1

i = 0
ans = 0
while i ** 2 < 10 ** n:
    t = [0] * 10
    for t_i in str(i ** 2):
        t[int(t_i)] += 1
    if s[1:] == t[1:]:
        ans += 1
    i += 1

print(ans)

E問題

各Sについて
tを先頭からx文字、後ろからy文字を含んでるとする
この時、すでに見たものの中で
後ろからlen(t)-x文字以上含んでいるもの　+　前からlen(t)-y文字以上含んでいるものの総和

E

class BinaryIndexTree:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def range_sum(self, i, j):
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i - 1)


n, t = input().split()
front = BinaryIndexTree(len(t) + 10)
back = BinaryIndexTree(len(t) + 10)
ans = 0
for i in range(int(n)):
    s = input()
    x = 0
    for s_i in s:
        if s_i == t[x]:
            x += 1
        if x == len(t):break
    y = 0
    for s_i in s[::-1]:
        if s_i == t[-y - 1]:
            y += 1
        if y == len(t):break

    # 0だとバグるので+1
    ans += i - front.sum(len(t) - y) + i - back.sum(len(t) - x)
    front.add(x + 1, 1)
    back.add(y + 1, 1)

    i = 0
    for s_i in s + s:
        if i < len(t) and t[i] == s_i:
            i += 1
    if i == len(t):
        ans += 1

print(ans)