ABC430 C – Truck Driver

C - Truck Driver

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

入力例1で考えていく

• A = 4以上
• B = 2未満

まずはaとbの累積和を求める

その後、lを固定した時に2分探索でaとbの条件に当てはまる場所ra,rbを探す（bは逆に考えて2以上であれば条件を満たすと考える）

l = 4の時、r = 8であれば、a[8] - a[4] = 4となりそれ以降はAの条件を満たす ・・・ra = 8

同じくl = 4の時、r = 10では、b[10] - b[4] = 2となりそれ以降はBの条件を満たす ・・・rb = 10

rb から ra を引くと特定のlの時に条件を満たす個数がわかる

これを0からnまで試す

ただし、raの方が大きい場合は条件を満たしていないのでカウントしない

以下でACできました。

def i_map(): return map(int, input().split())
def i_list(): return list(map(int, input().split()))

n, a, b = i_map()
s = list(input())

sa = [0]
sb = [0]
for i in range(n):
  if s[i] == 'a':
    sa.append(sa[-1]+1)
    sb.append(sb[-1])
  else:
    sb.append(sb[-1]+1)
    sa.append(sa[-1])

def fa(l):
  ok = n+1
  ng = l
  while ng < ok:
    mid = (ng + ok) // 2
    if sa[mid] - sa[l] >= a:
      ok = mid
    else:
      ng = mid + 1
  return ok

def fb(l):
  ok = n+1
  ng = l
  while ng < ok:
    mid = (ng + ok) // 2
    if sb[mid] - sb[l] >= b:
      ok = mid
    else:
      ng = mid + 1
  return ng

ans = 0
for l in range(n):
  ra = fa(l)
  rb = fb(l)
  if ra < rb:
    ans += (rb - ra)

print(ans)Code language: Python (python)

今回解くためのキーワード

• 単調性
  • 実数や整数に対して統一的に定義される条件について、ある値 x が存在して、x 以上では常に条件が成立する / しない、かつ x 未満では常に条件が成立しない / する。
    • https://atcoder.jp/contests/abc192/editorial/782
  • 2分探索などが使える

• 累積和
  • lからrまでのaやbの個数を求めるときに利用した
  • lからrまで全探索してaやbの個数を求めると時間がかかる

今回も解説放送わかりやすかった。感謝。