【競プロ】1日1AC : ARC99 C問題

今日で7日目です。キリがいいですね。今日は2記事も更新してえらい！

今日の問題はこちら

Difficultyは471（茶）です。
（AtCoder Problemsより）

余裕のある方は記事を読み進める前に解いてみてくださいね。

提出コードと考えたこと

具体例や図を載せておきます

値が全て1になるように、範囲を指定して置き換えていきます。数列のどこに1があっても上の図のように、範囲を表すバーは段々に整理できます。実際にバーを選ぶ順番を調整すれば、全て1に変えることができますね。
一番右のバーを除いて、バー同士の共通する長さは1だけにすることで最小回数で操作を終えられます。

以下が提出コードです。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i = 0;i < n;i++) cin >> a[i];
    int ans = 0;
    while(n != 0){
        if(n > k) n -= k - 1;
        else n = 0;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

1回の操作で \( K-1 \) 個が新たに1になるので、\( N \) から \( K-1 \) が何回引けるのかをカウントします。結局与えられる数列によらない答えになるわけですね。
（提出コードは答えを出すのに面倒なことをしていますが \( \displaystyle \left\lceil \frac{N-1}{K-1} \right\rceil \) にまとめられます）