ABC146 F - Sugoroku
解法
最小回数で到達できないといけないので,1回あたりでできるだけ先に進む必要がある.
また,辞書順で最小ということは,最初の方はなるべく小さい歩数でいきたい.
ということを考えると,
最初の方は控えめ→あとの方でなるべく大きく進む
と進むのが最善そうである.
これを考えると,後ろから遡ってなるべく左端から自分の今いるところに到達できるように繰り返していけば良さそう.
よって,現在いる場所をidxとして,以下を実装すれば良い.
1.idx=Nからスタート
2.if(idx<=M)s[0]=='0'が確約されているので,idx分戻れば良くて,これで終了
else M個前から順に見ていって,s[idx-j]=='0'が初めて満たされるjだけ遡れば良い
idx-=jと更新して2を繰り返す.