ABC363をPythonで（A～C,E）

AtCoder Beginner Contest 363の解答等のまとめ

A問題

次の対象のレートを求めて差を出力。

A

r = int(input())
n = ((r // 100) + 1) * 100
print(n - r)

B問題

$L$を降順でソートして、$p$番目が何日あれば$t$になるか計算する。

B

n, t, p = map(int, input().split())
L = sorted(map(int, input().split()), reverse=True)

print(max(0, t - L[p - 1]))

C問題

Pythonで通らなかったのでchatGPTでC++に変換したこのコードでACした。

並べ替え全通りにおいて、長さ$k$の回文があるか全部調べるといいはず。

変換前のPythonコード↓

C

from itertools import permutations

def in_palindrome(s):
    for now in range(n - k + 1):
        if all(s[now + i] == s[now + k - i - 1]for i in range(k // 2)):
            return True
    return False


n, k = map(int, input().split())
s = input()
check = set()
ans = 0
for p in permutations(s):
    if p in check:
        continue
    check.add(p)
    if not in_palindrome(p):
        ans += 1

print(ans)

D問題

＜考察・感想＞
各桁内にある回文数は$9 \times 10 ^{(桁数-1)}$個。
あとは端数調整すればいいはずだと思っているが、うまくいかなかった。

E問題

これもPythonで通らなかったのでchatGPTでC++に変換したこのコードでACした。

各年ごとに、その区画からその隣接区画へ水が流れるようにUnionFindで繋げる。
外側の区画は高さが一致したら海として設定した1マスとUnionFindで繋げる。
そして海と繋がっていない区画の数が答えになる。

変換前のpythonコード↓

E

from collections import defaultdict

class UnionFind:
    """
    URL : https://note.nkmk.me/python-union-find/
    """
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]


def main():
    h, w, y = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]

    UF = UnionFind(h * w + 10)
    sea = h * w + 5
    data = []
    for i in range(h):
        for j in range(w):
            data.append([a[i][j], i, j])

    data.sort()

    now = 0
    for i in range(1, y + 1):
        while now < h * w and data[now][0] <= i:
            _, x_i, y_i = data[now]
            for x_j, y_j in [(x_i + 1, y_i), (x_i - 1, y_i), (x_i, y_i + 1), (x_i, y_i - 1)]:
                if 0 <= x_j < h and 0 <= y_j < w:
                    if a[x_i][y_i] >= a[x_j][y_j]:
                        UF.union(x_i * w + y_i, x_j * w + y_j)
                else:
                    UF.union(x_i * w + y_i, sea)

            now += 1
        print(h * w - UF.size(sea) + 1)


main()