This page looks best with JavaScript enabled

AtCoderRegularContest099C Minimization

 ·   ·  ☕ 3 min read  ·  ✍️ reud · 👀... views

最高にバグる!

C - Minimization

友人と例のごとくバチャやってたらこの問題出てきてとてつもなくひどい目にあった。

前にも解いているのに解けない。

かなり悔しいので解き直すことにする。

解法 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が天才すぎる。

Share on

reud
WRITTEN BY
reud
Stundent