Sugoroku [AtCoder Beginner Contest 146 F]

https://atcoder.jp/contests/abc146/tasks/abc146_f

解説

https://atcoder.jp/contests/abc146/submissions/8635768

DPして復元する。
後ろからまずは最短手数になるようにDPしよう。
i番目のマスが0で最短距離がdp[i]であれば、dp[i-1]～dp[i-M]がdp[i]+1で更新される。
この区間min代入は遅延評価セグメントツリーで殴れる。
これで殴っとこう。

あとは、先頭から順番に一番近いその数の所を探してくればいい。
これは数毎に添字を持っておき、upper_boundとかで取ってくればいい。

int N, M; string S;
LazySegTree<int, 1 << 17> lst;
vector<int> idx[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> S;

    lst.update(N, N + 1, 0);
    rrep(i, N, 0) if(S[i] == '0') {
        int mi = lst.get(i, i + 1);
        int l = max(0, i - M);
        lst.update(l, i, mi + 1);
    }
    
    if (lst.get(0, 1) == inf) {
        cout << -1 << endl;
        return;
    }

    rep(i, 0, N + 1) if (S[i] == '0') idx[lst.get(i, i + 1)].push_back(i);

    vector<int> ans;
    int cu = 0;
    int dp = lst.get(0, 1);
    while (cu < N) {
        int nxt = *upper_bound(all(idx[dp - 1]), cu);
        ans.push_back(nxt - cu);
        cu = nxt;
        dp--;
    }

    int n = ans.size();
    rep(i, 0, n) {
        if (i) printf(" ");
        printf("%d", ans[i]);
    }
    printf("\n");
}