はまやんはまやんはまやん

hamayanhamayan's blog

Decrease (Contestant ver.) [AtCoder Regular Contest 079 D]

http://arc079.contest.atcoder.jp/tasks/arc079_b

解法

http://arc079.contest.atcoder.jp/submissions/1463985

重要な性質がある
「全ての要素に1回ずつ操作を行うと、全て均等に-1される」

ここでNは50で固定して考えてみると、考えるKは50未満であることが分かる。
これは、50 <= Kであれば、Kから50を引いて全て均等に+1していくことで、Kを50未満にできるからである。

まず、小さいKについて考えてみると

K = 0 {49, ..., 49}
K = 1 {48, ..., 48, 50}
K = 2 {47, ..., 47, 50, 50}
...
K = 49 {0, 50, ..., 50}

のように、最後にK個だけ50がつき、それ以外は、49-Kで埋められていることが分かる。

これを実装すると答えとなる。

typedef long long ll;
vector<ll> build(ll K) {
    vector<ll> ans;
 
    ll d = K % 50;
    rep(i, 0, 50 - d) ans.push_back(49 - d);
    rep(i, 0, d) ans.push_back(50);
 
    ll a = K / 50;
    rep(i, 0, 50) ans[i] += a;
 
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    ll K; cin >> K;
 
    auto ans = build(K);
    int n = ans.size();
    printf("%d\n", n);
    rep(i, 0, n) {
        if (i) printf(" ");
        printf("%lld", ans[i]);
    }
    printf("\n");
}