問題

B – 直線塗り

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

atcoder.jp

記録

• 2022/1/15 解法わからず。

解法

1. どれだけ移動する必要があるかを考えると、最も右の . の場所から \(R+1\) を引いたところまで移動する必要がある。
2. 何回インクを発射する必要があるかを考えると、最も左の . の場所でインクを発射すると \(R\) 先まで塗る必要がない。これを繰り返す。

コード例1

#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 << 60;
// const int INF = 1001001001;

int main() {
  int N, R;
  cin >> N >> R;

  string S;
  cin >> S;

  int n = S.size();

  int move = 0;
  rep(i, n) {
    if(S[i] == '.') {
      move = max(0, i - R + 1);
    }
  }

  int paint = 0;
  int current = 0;
  while(current < n) {
    if(S[current] == '.') {
      paint++;
      current += R;
    } else {
      current++;
    }
  }

  cout << move + paint << endl;
  return 0;
}