ABC146-F

時間内にたどり着けなかったけど、たぶん後ろから貪欲にとれば、辞書順最小だな。

j回でたどり着けるとして、j回目の出目をとすると、なので、辞書順最小は後ろからとれるだけとるのが最適なはず。
一度、後ろから累積minを取ってやると楽ちん。

def max(a,b); a > b ? a : b; end
  
N, M= gets.split.map(&:to_i)
S = gets.chomp
smin = Array.new(N + 1, N)

(0 .. N).reverse_each.inject(N) do |m,i|
  if i + M < m
    puts -1
    exit
  end
  smin[i] = S[i] == '0' ? i : m
end

ANS = []
N.times.inject(N) do |pos,i|
  break if pos.zero?
  smin[max(pos - M, 0)].tap do |j|
    ANS << pos - j
  end
end
puts ANS.reverse * ' '