問題概要 (ARC 099 C / ABC 101 C)
1〜N の順列が与えられる。以下の操作を最小回数繰り返すことにより、全部 1 にせよ。
制約
- 1 <= K <= N <= 105
解法
間違いやすい嘘解法として、「1」から外側にどんどん広げるというものがある。これだと両端が少しだけ残って損をすることがある。
今回の問題は以下のように言い換えることができる:
これを達成しない限り「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; } }