ABC360Dを解いた

筆者はレート600前後の茶色コーダ

この前開催されたABC360で解けなかったD問題を解説ACしたので備忘録

問題ページ

実装コード

S[i] が 1, 0の集団に分け、それぞれをソート
それぞれの解の上限、下限をしゃくとり法で計算して足せばOK

import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,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, T = rLI()
    S = rS()
    X = rLI()
        
    bn = []
    len_bn = 0
    bp = []
    for i in range(N):
        if S[i] == '0':
            bn.append(X[i])
            len_bn += 1
        else:
            bp.append(X[i])
    bn.sort()
    bp.sort()
    ans = 0
    l = 0
    r = 0
    for p in bp:
        while l < len_bn and p > bn[l]: 
            l += 1
        while r < len_bn and p + 2 * T >= bn[r] :
            r += 1
        ans += r - l
    print(ans)
if __name__ == '__main__':
    main()

まとめ

ABC360Dを解いた、解法にはしゃくとり法を使用した

感想

今回の問題はしゃくとり法を使う所までは検討が着いたが、
解の上限、下限を計算する方法が思いつかなかった、
この部分は数学よりな話だと思うので、そこら辺の地力も必要だと感じた。