ABC257C - Robot Takahashi

方法1：1コずつずらす

考え方

$X$としては現れる体重だけを調べれば良い．

体重をソートして一番小さい場合から順に，正しく判定できている人数を調べれば答えがわかる．

回答例

N = int(input())
S = list(input())
W = list(map(int, input().split()))

WS = [(w, s) for w, s in zip(W, S)]
WS.sort()

cnt_ad = 0
cnt_chi = 0
for w, s in WS:
    if s == '1':
        cnt_ad += 1

ans = cnt_ad
for i in range(N):
    w, s = WS[i]
    if s == '0':
        cnt_chi += 1
    else:
        cnt_ad -= 1
    if i != N - 1 and w == WS[i + 1][0]:continue
    ans = max(ans, cnt_chi + cnt_ad)

print(ans)

方法2：bisect

考え方

子供だけの体重リストと，大人だけの体重リストを作っておく．「ある体重以上の大人」や「ある体重未満の子供」はbisectで求められる．

ただし，「未満」のほうを正しく求めるためには，max(W) + 1も調べる必要がある．

回答例

from bisect import bisect_left

N = int(input())
S = list(input())
W = list(map(int, input().split()))

w_ad = []
w_chi = []
for i, w in enumerate(W):
    if S[i] == '0':
        w_chi.append(w)
    else:
        w_ad.append(w)

w_ad.sort()
w_chi.sort()

adults = len(w_ad)
num_ad = [0] * (N + 1)
num_chi = [0] * (N + 1)
for i, w in enumerate(W + [max(W) + 1]):
    ind_ad = bisect_left(w_ad, w)
    ind_chi = bisect_left(w_chi, w)
    num_ad[i] = max(0, adults - ind_ad)
    num_chi[i] = ind_chi

ans = 0
for i in range(N + 1):
    ans = max(ans, num_ad[i] + num_chi[i])

print(ans)