解法 1: 最小値の左にある要素数と右にある要素数を考える。

配列Aの最小値は問題の制約から1です。

解き方

0-indexedで入力値を配列Aに入れていきます。
v[i] = 1になるようなiの場所を見つけます。
left = i, right = N - i - 1とします。それぞれ、left = {最小値より左にある要素の数} right = {最小値より右にある要素の数}　となります。
一度塗りつぶせる最小値以外の要素 power = K - 1とする。
最小値から左にある要素を最小値で塗りつぶす回数 left_cost = ceil(left/power)
ここでleft_costで塗り潰せるマス数 mass = left_cost * (K-1) とする。
mass > leftの場合、無駄な手数が発生してしまうので余剰分をrightから引く。 right -= (mass - left)
最小値から右にある要素を最小値で塗りつぶす回数 right_cost = ceil(right/power)
left_cost * right_cost を出力して終了。

ソースコード

提出 #16755795 - AtCoder Regular Contest 099

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


#include <bits/stdc++.h>
#define INF 1e9
#define INFLL 1ull<<60u
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

void solve() {
    int N,K; cin >> N >> K;
    vector<int> v(N);
    REP(i,N) cin >> v[i];

    REP(i,N) {
        if (v[i] != 1) continue;
        // cerr << i << endl;
        auto left = i;
        auto right = N - i - 1;

        auto left_cost = (i+K-1-1)/(K-1);
        if (left_cost && (left_cost * (K-1)) > left) right -= (left_cost * (K-1)) - left;

        chmax(right,0);
        auto right_cost = (right+K-2)/(K-1);
        cout << left_cost+right_cost << endl;
    }
    assert("bugged");
}


int main() {
    solve();
    return 0;
}

解法 2: 操作手順が並び替え可能であることを利用する。

kanadeさんに教えてもらった解法

操作手順が並び替え可能であること、操作回数さえ出せば良いことを利用して解きます。

0-indexedで入力値を配列Aに入れていきます。
分かりやすくするため、 A = [a,b,c,d,e,f,g], K = 3 とします。 (a > … > g)
前からK個について操作をします。 A = [c,c,c,d,e,f,g]
操作されていない範囲について前からK-1個ずつ変換します。ここで、変換値は変換対象の最小要素
A = [c,c,e,e,e,f,g] → A = [c,c,e,e,g,g,g]
ここで並び替えの手順を変えれば、(今回で言えば操作を真逆にすれば)全て最小値に出来ます。(操作手順を変えれば、全てを最小値をに出来ることはどの配列でも満たします)

すなわち、要素数NからKを引いて、一回の操作、その後(N-K)を(K-1)で割って繰り上げた値がその後の操作回数となります。

これだと配列の値を読む必要すらなくなるので良いです。

提出 #16755913 - AtCoder Regular Contest 099

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


#include <bits/stdc++.h>
#define INF 1e9
#define INFLL 1ull<<60u
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

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


int main() {
    solve();
    return 0;
}

感想

解答2が天才すぎる。