ABC375をPythonで（A～D）

パナソニックグループ プログラミングコンテスト2024（AtCoder Beginner Contest 375）の解答等の速報的まとめ

A問題

先頭から順番に条件を満たしているか確かめる

A

n = int(input())
s = input()

ans = 0
for i in range(n - 2):
    if s[i:i+3] == "#.#":
       ans += 1

print(ans)

B問題

スタートとゴールが$(0, 0)$であることに気を付けて距離を足し合わせる

B

def diff(a, b, c, d):
    return ((a - c) ** 2 + (b - d) ** 2) ** 0.5

n = int(input())
data = [list(map(int, input().split())) for _ in range(n)]
data = [[0, 0]] + data + [[0, 0]]

ans = 0
for (x_i, y_i), (x_j, y_j) in zip(data, data[1:]):
    ans += diff(x_i, y_i, x_j, y_j)

print(ans)

C問題

結局のところ外側からの距離に応じて決まった回数だけ回転しているので、各座標ごとに参照箇所が計算で求められる

C

def move(x, y, cnt):
    if cnt % 4 == 0:
        return x, y
    elif cnt % 4 == 1:
        return n - y - 1, x
    elif cnt % 4 == 2:
        return n - x - 1, n - y - 1
    else:
        return y, n - x - 1

n = int(input())
a = [list(input()) for _ in range(n)]
ans = [["."] * n for _ in range(n)]

for i in range(n):
    for j in range(n):
        x, y = move(i, j, min(i + 1, j + 1, n - i, n - j))
        ans[i][j] = a[x][y]

for a_i in ans:
    print("".join(a_i))

D問題

これの答えは同じ文字同士の間にある文字の個数の総和になる
よって線形時間で解を求めるには、各文字において既に出た同じ文字との間にある文字数の総和が計算できれば良い

これは
$($今の座標$-1)\times($既に出た同じ文字の個数$) - ($既に出た同じ文字の座標の和$)$
で求められる

D

s = input()

ans = 0
sum = {chr(i + ord("A")) : 0 for i in range(26)}
cnt = {chr(i + ord("A")) : 0 for i in range(26)}

for i, s_i in enumerate(s):
    ans += (i - 1) * cnt[s_i] - sum[s_i]
    sum[s_i] += i
    cnt[s_i] += 1

print(ans)