ABC381Eを解いた【累積和,二分探索】

Python AtCoder 競技プログラミング

筆者はレート800前後の茶～緑コーダ

ABC381のE問題を解いていく

実装コード

• 各文字の出現個数を累積和で求める
• "/"の位置を二分探索
• チェックする"/"がクエリ範囲なら、"/"の左にある1の個数、右にある2の個数の少ない方の2倍に1を足した数が暫定の答え
• 少ない方に合わせて探索する/の位置をずらす

main.py

from itertools import accumulate
import sys

def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)


def main():
    N, Q = rLI()
    S = rS()
    c = {k:[0]*-~N for k in "12/"}
    M = 0    
    for i,s in enumerate(S, start=1):
        c[s][i] = 1
        if s=="/":M+=1
    c1 = list(accumulate(c["1"]))
    c2 = list(accumulate(c["2"]))
    cs = [i for i in range(-~N) if c["/"][i]==1]
    
    # err(c1)
    # err(c2)
    # err(cs)
    
    for _ in range(Q):
        l,r= rLI()        
        # err(f'l: {l}, r: {r}, li: {li}, ri: {ri}')
                
        ans = 0
        li = 0
        ri = M-1
        while li <= ri:
            mi = (li+ri)//2
            m = cs[mi]
            if m < l:
                li = mi + 1
                continue
            elif m > r:
                ri = mi - 1
                continue
            # err(f'mi: {mi}, m: {m}')
            
            l1 = c1[m] - c1[l-1]
            r2 = c2[r] - c2[m]
            # err(f'l1: {l1}, r2: {r2}')
            
            ans = max(ans,2*min(l1,r2)+1)
            
            if l1>r2:
                ri=mi-1
            else:
                li=mi+1

        # err(f"ans: {ans}")
        print(ans)
    
if __name__ == '__main__':
    main()

まとめ

ABC381のE問題を解いた。
解法には累積和と二分探索を組み合わせた

同コンテストのD問題の解説よりわかりやすかったが、bisectの使い方に苦戦して結局直接実装する方式に落ち着いた。

もう少しライブラリの使い方を把握しておきたい