ARC079 D : Decrease (Contestant ver.)(600)
作成日：2017.07.30
最終更新日：2017.07.30
問題概要
長さ$N$の非負整数列$\{a_i\}$に対し、$max\{a_i\} \leq N-1$となるまで、
<操作>「数列の最大の要素のうちの一つを選び、その要素の値を$N$減らし、それ以外の要素の値を$1$増やす」を行う。
この操作の回数がちょうど$K$になるような数列を1つ求めよ。
但し、$2 \leq N \leq 50 , 0 \leq a_i \leq 10^{16} + 1000$を満たす必要がある。
制約
$1 \leq K \leq 50 \times 10^{16}$
考え方
操作し終えた数列$\{b_i\}$に対し操作を巻き戻していく、つまり、ある要素を選んでその値を$N$増やし、他の要素の値を$1$減らす操作を考える。
まず、同じ要素$b_1$が繰り返し$x$回選ばれることを考える。
すると$b_1$は$b_1 + N x$に、$b_i(i \neq 1)$は$b_i - x$となる。
しかし、これは$0$未満になり得ず、$b_i \leq N-1$であるから$x \leq N-1$である。
また同様の議論により、はじめから同じ要素が選ばれないのは連続で$N-1$回以下である。
つまりはじめの$N$回の操作で各要素1回ずつ選ぶ必要がある。
この時、各要素は$1$ずつ増えている。
このように各要素を$N$回に1回選んでいけば良さそうである。
$K$が$N$で割り切れない時も余りの数だけ異なる要素を選ぶことを考える。
$q = K / N , r = K \% N$とすると、余分に選んだ要素は$q+N-r+1$増え、そうでない要素は$q-r$増える。
$r \leq N-1$であるから、$b_i = N-1$であれば要素が途中で負になることはない。
また、$a_i$及び$K$の制約から$N=50$であれば良いことが分かる。
ソースコード
マクロ等はこちら
LL K;
int main(){
scanf("%lld" , &K);
int N = 50;
LL q = K / N;
LL r = K % N;
printf("%d\n" , N);
repp(i,0,N){
printf("%lld%c" , N - 1 + q - r + (i<r?N+1:0) , i+1==N?'\n':' ');
}
return 0;
}解法まとめ
$N=50$とする。(5行)
$K$を$N$で割った商を$q$、余りを$r$として、$r$個は$N-1+(q-r+N+1)$、残りは$N-1+(q-r)$を出力する。(6-11行)