エクサウィザーズ2019

ExaWizards 2019 - AtCoder

C - Snuke the Wizard

愚直にやってしまいTLEでした..

左に落ちるゴーレムのうち一番みぎにいるやつと、右に落ちるゴーレムのうち一番左にいるやつを求めれば良い。二分探索で求めると早くできる。 らしいけど、コードが全く通らないです、誰かのコードを見たすぎる

N, Q = map(int, input().split())
s = input()
t_list, d_list = [], []
for _ in range(Q):
    t, d = input().split()
    t_list.append(t)
    d_list.append(d)

    
def if_survive(idx):
    """
    Args :
        idx : position of gorem
        max_ : max value of position idx
        min_ : min value of position idx
    Return : 
        +1 : 右側に落ちた時
        -1 : 左側に落ちた時
        0 : 落ちなかった時
    """
    max_ = len(s) - 1
    min_ = 0
    target_moji = s[idx]
    current_position = idx
    
    for t, d in zip(t_list, d_list):
        if t == target_moji:
            if d == "L":
                current_position -= 1
            elif d == "R":
                current_position += 1
                
            if current_position > max_:
                return 1
            elif current_position < min_:
                return -1
            target_moji = s[current_position]

        else:
            pass
    return 0

# 二分探索
def bisection_search_right(x_max, x_min):
    if if_survive(x_max) < 1:
        return x_max + 1
        
    while(True):
        x_mid = int((x_max + x_min)/2)
        max_survive = if_survive(x_max)
        mid_survive = if_survive(x_mid)

        if mid_survive + max_survive == 2:
            x_max = x_mid
        elif mid_survive + max_survive < 2:
            x_min = x_mid
        
        if x_max - x_min == 1:
            return x_max
        
def bisection_search_left(x_max, x_min):
    if if_survive(x_min) > -1:
        return x_min - 1
    
    while(True):
        x_mid = int((x_max + x_min)/2)
                
        min_survive = if_survive(x_min)
        mid_survive = if_survive(x_mid)

        if mid_survive + min_survive == -2:
            x_min = x_mid
        elif mid_survive + min_survive > -2:
            x_max = x_mid
        
        if x_max - x_min == 1:
            return x_min
    
right_idx = bisection_search_right(N-1, 0) 
left_idx = bisection_search_left(N-1, 0) 

print(N - (left_idx+1) - (N-right_idx))