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; }
