ABC327をPythonで（A~E）

HHKBプログラミングコンテスト2023(AtCoder Beginner Contest 327)

A問題

ab か ba のどちらかが入っているか確認

A

input()
s = input()
print("Yes" if "ab" in s or "ba" in s else "No")

B問題

答えとなるAの数は少ないので全探索

B

b = int(input())
a = 1
while a ** a <= b:
    if a ** a == b:
        print(a)
        exit()
    else:
        a += 1

print(-1)

C問題

全部がんばって調べる

C

a = [list(map(int, input().split())) for _ in range(9)]

if any(len(set(a[i])) < 9 for i in range(9)):
    print("No")
    exit()

x = [set() for _ in range(9)]
for i in range(9):
    for j in range(9):
        x[j].add(a[i][j])

if any(len(x_i) < 9 for x_i in x):
    print("No")
    exit()

y = [set() for _ in range(9)]
for i in range(9):
    for j in range(9):
        y[i // 3 + j // 3 * 3].add(a[i][j])

if all(len(y_i) == 9 for y_i in y):
    print("Yes")
else:
    print("No")

D問題

$s_i$と$t_i$を辺でつないだグラフが2部グラフか判定すればよい

D

from collections import deque

n, m = map(int, input().split())
s = list(map(lambda x:int(x) - 1, input().split()))
t = list(map(lambda x:int(x) - 1, input().split()))

edge = [[] for _ in range(n)]
for s_i, t_i in zip(s, t):
    edge[s_i].append(t_i)
    edge[t_i].append(s_i)

def bfs(start):
    global dist, check
    q = deque()
    q.append(start)
    check[start] = True
    dist[start] = 0
    while q:
        now = q.popleft()
        for to in edge[now]:
            if check[to]: continue
            check[to] = True
            dist[to] = (dist[now] + 1) % 2
            q.append(to)

check = [False] * n
INF = float("inf")
dist = [INF] * n
for i in range(n):
    if not check[i]:
        bfs(i)

for s_i, t_i in zip(s, t):
    if dist[s_i] == dist[t_i]:
        print("No")
        exit()

print("Yes")

E問題

dpを使い、レート計算式の前の項の分子の最大値を使った個数ごとに求め、あとで正しいレートを計算する

E

from math import sqrt

n = int(input())
p = list(map(int, input().split()))

INF = float("inf")
dp = [0] + [-INF] * n
for i, p_i in enumerate(p):
    new_dp = [0] * (n + 1)
    for j in range(1, i + 2):
        new_dp[j] = max(dp[j], dp[j - 1] * 0.9 + p_i)
    dp = new_dp

ans = -INF
x = 0
for i, d_i in enumerate(dp[1:], 1):
    x += pow(0.9, i - 1)
    ans = max(ans, d_i / x - 1200 / sqrt(i))

print(ans)