ARC 099 C - Minimization

問題概要 (ARC 099 C / ABC 101 C)

1〜N の順列が与えられる。以下の操作を最小回数繰り返すことにより、全部 1 にせよ。

連続する K 個の区間を選んで、その区間のすべての数をその区間にある最小の数に置き換える

制約

1 <= K <= N <= 10⁵

解法

間違いやすい嘘解法として、「1」から外側にどんどん広げるというものがある。これだと両端が少しだけ残って損をすることがある。

今回の問題は以下のように言い換えることができる:

交差している区間は互いに行き来できるものとする。最小個数の区間を置いて、1〜N全体を行き来できるようにせよ。

これを達成しない限り「1」を全体に行き渡らせることはできないし、逆にこれを達成できれば「1」を全体に行き渡らせることができる。

#include <iostream>
#include <vector>
using namespace std;

int N, K;
vector<int> A;

int main() {
  while (cin >> N >> K) {
    A.resize(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    int res = 0;
    int right = 0;
    while (true) {
      if (res == 0) right += K;
      else right += K-1;
      ++res;

      if (right >= N) break;
    }
    cout << res << endl;
  }
}