エクサウィザーズ2019
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))