hogecoder

tsutaj 競技プログラミングの記録

AtCoder Regular Contest 079 D: Decrease (Contestant ver.)

AtCoder 数学

どうやら自分の解法が想定解法と違うみたいなので、別解をブログに残しておきます。

問題概要

日本語なので原文参照 → D: Decrease (Contestant ver.) - AtCoder Regular Contest 079 | AtCoder

解説

まず、出力する数列の長さは N = 50 に固定してしまいます。この方が大きな入力にも対応できるからです。(もちろん、小さな入力にも対応できる)

i 番目の要素の値を a_{i}、また i 番目の要素に対して操作を行う回数を s_{i} と表すことにします。

まずは、 s_{i} の値がなるべく均等になるように操作回数を各要素に配分しましょう。すると、 i 番目の要素の値は、他の要素で操作を行うことで \sum_{1 \leq j \leq N, j \neq i} s_{j} 増えることがわかります。この増分を D_{i} とします。

これで、 i 番目の要素は a_{i} + D_{i} という値まで増え、操作回数は s_{i} 回必要であることがわかりました。あとは、この情報を元に a_{i} を決めれば答えがわかります。

要素の値が N 以上なら操作を 1 回行う必要があり、 2N 以上なら 2 回・・・ということを考えると、このような式を満たせば良いことがわかります。

\displaystyle \lfloor \frac{a_{i} + D_{i}}{N} \rfloor = s_{i}

床関数があって扱いにくいので、変形します。

N \times s_{i} \leq a_{i} + D_{i} \lt N \times (s_{i} + 1)

したがって、

N \times s_{i} - D_{i} \leq a_{i} \lt N \times (s_{i} + 1) - D_{i}

この範囲に収まるように a_{i} を決定すれば良いことがわかりました。あとはこの範囲内の値になるように適当に決めたら良いです。

※注意: a_{i} の下限は 0 ですので、負の値にならないように気をつけましょう。

ソースコード

int K, rec[60], ans[60];
const int N = 50;

signed main() {
    cin >> K;
    int div = K / N, mo = K % N;
    rep(i,0,N) rec[i] = div + (i < mo);

    rep(i,0,N) {
        int sum = 0;
        rep(j,0,N) if(i != j) sum += rec[j];
        ans[i] = N * (rec[i] + 1) - sum - 1;
    }
    cout << N << endl;
    rep(i,0,N) cout << (i ? " " : "") << ans[i];
    cout << endl;
    return 0;
}