はまやんはまやんはまやん

hamayanhamayan's blog

Minimization [AtCoder Regular Contest 099 C]

https://beta.atcoder.jp/contests/arc099/tasks/arc099_a

考察

1. 300点ということもあるので、自明な所から攻めていこう
2. 順列が与えられているので、全ての要素を1にする必要がある
3. 全ての要素を書き換えるので、操作を繰り返すことで、全ての要素を網羅する必要がある
4. 操作回数の下界を考えると、N要素を長さKの区間で被覆するための最小個数ではないか
5. その下界は最適に行えば実現可能であるらしく、実際これでACが取れる

解説

https://beta.atcoder.jp/contests/arc099/submissions/2718616

N要素を長さKの区間で被覆するための最小個数がそのまま答えになる。
これは要素の中身に依存しないので、今回は答えを導くのに配列Aは使わない。
長さKの区間で被覆するが、操作の関係上、必ず1要素分かぶらせる必要があるため、ceil*1が最小個数となる。
ceilは切り上げであり、ceil(x/y)は(x + y - 1) / yで計算ができる。

int N, K;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
 
    int ans = (N - 1 + K - 2) / (K - 1);
    cout << ans << endl;
}

*1:N-1)/(K-1