No.672 最長AB列
解法
まず愚直解を考えます.
左端を決めて左から文字列を見ていき, A, B,の数を数えながら右に行き, AとBの数が同一になったら最大値を更新します.
この解法はでTLEです. この解法を詰めていきましょう.
まず,ABの数が同一ということはAを1, Bを-1とすると和が0となるということです. これの累積和をとっておき, 区間が与えられたらでその区間のABの数が同一かどうかを答えられるようにしておきます.
ある２つの区間の端を選ぶと, 対応する累積和があります. その累積和の差が0であると, その 区間のABの数は同一ということになります.
上の考察から, ある区間の左側を決めたときに, それに対応する累積和と同一のものが右側に存在するか？を考えればいいことがわかります.
このときに選ぶ右端は, できる限り右側のものを選ぶと, 区間が大きくなります.
よって, 累積和をとるときにある累積和の数値をとったもので最大の添字を持つものを一緒に保存しておけばいいことがわかります.
mapで上を実装すると, 計算量はで抑えられます.
感想
はじめは累積和をとって二分探索するものかと思いましたが, 単調性の反例が見つかり断念.
こういった問題は愚直解から詰めていかないと考察が難しいですね...
類題としてAGCのZero Sum Rangeなんかが挙げられます.
区間の左側を決めた時に最適な右側を高速で導出するのは結構典型ですね.
