日鉄ソリューションズプログラミングコンテスト2022(AtCoder Beginner Contest 257) 参戦記
集中できない理由があったので unrated で参加.
ABC257A - A to Z String 2
書くだけ.
N, X = map(int, input().split())
print(chr(ord('A') + (X - 1) // N))
ABC257B - 1D Pawn
素直にシミュレーションすればいい.
N, K, Q = map(int, input().split())
A = list(map(lambda x: int(x) - 1, input().split()))
L = list(map(lambda x: int(x) - 1, input().split()))
cells = [None] * N
for i in range(K):
cells[A[i]] = i
for l in L:
t = -1
for j in range(N):
if cells[j] is None:
continue
t += 1
if t == l:
break
if j != N - 1 and cells[j + 1] is None:
cells[j + 1] = cells[j]
cells[j] = None
result = [-1] * K
for i in range(N):
if cells[i] is None:
continue
result[cells[i]] = i + 1
print(*result)
ABC257C - Robot Takahashi
予め体重をソートしておけば、指定の体重未満、以上の人数をにぶたんにより $O(\log N)$ で求めれるようになるので、$O(N \log N)$ で解けた.
from bisect import bisect_left
N = int(input())
S = input()
W = list(map(int, input().split()))
a = sorted(W[i] for i in range(N) if S[i] == '0')
b = sorted(W[i] for i in range(N) if S[i] == '1')
c = set()
for x in W:
c.add(x - 1)
c.add(x)
c.add(x + 1)
result = 0
for x in c:
result = max(result, bisect_left(a, x) + len(b) - bisect_left(b, x))
print(result)
座標圧縮+累積和でも解けた.
from itertools import accumulate
N = int(input())
S = input()
W = list(map(int, input().split()))
a = sorted(W)
d = {}
for i in range(len(a)):
d[a[i]] = i + 1
W = [d[x] for x in W]
m = max(W)
b = [0] * (m + 2)
c = [0] * (m + 2)
for i in range(N):
if S[i] == '0':
b[W[i]] += 1
else:
c[W[i]] += 1
b = list(accumulate(b))
c = list(accumulate(c))
d = S.count('1')
result = 0
for i in range(m + 2):
result = max(result, b[i] + (d - c[i]))
print(result)