TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

 
 

Sugoroku

問題

F – Sugoroku
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

記録

解法

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
const int INF = 1001001001;

int main() {
  int N, M;
  string S;
  cin >> N >> M >> S;

  // 後ろからdp
  vector<int> dp(N+1, INF);
  dp[N] = 0;

  // 最小手数を管理するキュー
  queue<int> que;

  // dp[N] は 0
  que.push(0);

  for(int i = N-1; 0 <= i; --i) {
    while(1) {
      
      // 途中でキューのサイズが 0 になったら、
      // たどり着けない。
      if(que.size() == 0) {
        cout << "-1" << endl;
        return 0;
      }

      // 最大値が INF じゃない かつ
      // キューのサイズが M 以下になるまで
      // キューの最大値を捨てていく
      if(que.front() != INF && que.size() <= M) {
        break;
      } else {
        que.pop();
      }
    }

    if (S[i] == '0') {
      // 最小手数はキューの最大値 + 1
      dp[i] = que.front() + 1;
    }

    // 手数をキューに追加
    que.push(dp[i]);
  }

  vector<int> ans;
  int current = 0;
  int v = dp[0];
  while (current < N) {
    // 近くの v-- まで移動したい
    // (辞書順最小にしたいから)
    v--;

    // 移動すべき目の数を求める
    int i = 1;
    while (dp[current + i] != v) {
      ++i;
    }

    ans.push_back(i);
    current += i;
  }

  rep(i, ans.size()) {
    cout << ans[i] << " ";
  }
  cout << endl;
  return 0;
}