ABC-360

A

$URL\:\to$

解法

---

B

$URL\:\to$

解法

---

C

$URL\:\to$

解法

---

D

$URL\:\to$ https://atcoder.jp/contests/abc360/tasks/abc360_d

#尺取り法 #二分探索

n,t = Integer().content
s = Word().content
x = IntegerList().content

tl,tr = [],[]
for i in range(n):
  if s[i]=='0': tl.append(x[i])
  else: tr.append(x[i])

tl.sort(); tr.sort()
tr = IntegerList(tr).content; tl = IntegerList(tl)

# 尺取り or 二分探索(今回)
ans = 0
for i in tr:
  ans += tl.upperBound(i+2*t) - tl.upperBound(i)

print(ans)

解法

模範解答は尺取りで実装しているが、二分探索の方が気軽なので今回は二分探索で実装する。 正に進むのか負に進むかで仕分けしたのちに、動く前と動いた後(つまるところ、$\boldsymbol2T$増減させた)でそれぞれ二分探索を行い、値の差をとる。 また、$\boldsymbol{2T}$ 増減させるのは二分探索に使用される方の配列の値は変えたくないからであり、二分探索するときに返却値は絶対値的に大きい方を返さないとバグる(はず)。

---

E

$URL\:\to$

解法

---