M,+,-の3文字の列が与えられて、Mごとに数直線上のどちらかに移動し、+,-で点数を+,-していく。最後に原点に戻ってくる条件の元、最大の点数を考える問題。dpは一瞬で思いついたけど、それじゃあ絶対len(S) == 1e5という制約は満たせないのは明らかだった。…