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()