ARC099(ABC101): C - Minimization

問題

C - Minimization

解説

最小値で置き換えると書いてあるが、最小値は自明に1である。しかし、個で1を広げていこうとすると、左[右]端で生じる無駄を排除する方法で悩むことになる。個人の感想だが、問題を読解しただけの自明思考をそのまま使って解答を試みると大抵ハマる。

今回の問題で、数字は1とそれ以外の数字とで分けられる。数字の情報はもはや余計なので、問題は以下のように言い換えて良い。

一次元上に、個の白と黒のマスがある。連続するマスを黒く塗りつぶすことができる。塗りつぶす時は黒マスが1マス以上重なるように塗る必要がある。最小何回で全てを黒マスに塗りつぶせるだろうか。また、初めの黒マスの個数は1個である。

ここで、使う順序・塗りつぶす順序を問わない、というのはよくある貪欲法の考えである。

それらを念頭に、最小の塗りつぶし回数を考えると、左端で個埋めて、続きは黒マスの重なりを考えて個ずつ貪欲でマスを埋めていけば良い事がわかる。実際は黒マスを含む区間を先に塗ったものと考えれば問題文に適合する。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, K; cin >> N >> K; // N個の数値の入力は無価値
  // cout << (1 + (N - K) / (K - 1) + ((N - K) % (K - 1) > 0)) << "\n"; // 汚いコード
  cout << ceil(double(N - 1) / (K - 1)) << "\n"; // 綺麗なコード. 1度に最大K-1個までしか黒マスを増やせないと考えて解く
}