ARC079 E : Decrease (Judge ver.)(600)
作成日：2017.07.30
最終更新日：2017.07.30
問題概要
長さ$N$の非負整数列$\{a_i\}$に対し、$max\{a_i\} \leq N-1$となるまで、
操作「数列の最大の要素のうちの一つを選び、その要素の値を$N$減らし、それ以外の要素の値を$1$増やす」を行う。
数列が与えられるので、この操作を行う回数を求めよ。
制約
$2 \leq N \leq 50$
$0 \leq a_i \leq 10^{16} + 1000$
考え方
答えを$K$とおいてこれが取り得る値を考えたい。
そのために問題の条件から$0$以上$N-1$以下であることが分かっている、操作が終わった時の数列の各要素の値$b_i$を求める。
数列の各要素$a_i$が最大の要素として選ばれる回数を$p_i$とおくと、$\sum{p_i} = K$であり、
$b_i = a_i + (K-p_i) - N p_i = a_i + K - (N+1)p_i$である。
$p_i$を消去するために$i$について総和を取り不等式評価をすると、$0 \leq b_i \leq N-1$より$0 \leq \sum{a_i} - K \leq N(N-1)$である。
よって$s = \sum{a_i}$とおくと、$s - N(N-1) \leq K \leq s$である
(このことは操作を1回行うたびに数列の総和が$1$減ることからも分かる)。
答えの候補は$N(N-1)+1 \leq 2451$と十分に小さいので、各候補が適切であるかを判定できれば良い。
明らかに不適なのは$K < 0$の時と、$b_i < 0 , N \leq b_i$の時である。
よって前の段落での考察より、$b_i = (a_i + K) \% (N+1)$かつ$b_i \neq N$である。
また、同じく前の段落での考察より$\sum{b_i} = s - K$とならないのも不適である。
$p_i$と$b_i$は一対一対応していることから、あとは以上の条件を満たした時に、操作を繰り返す中で最大の要素が$N-1$以下になったのに操作を続けているということがないことを保証できれば良い。
これは、条件を満たす$K$のうち最小のものがこれに反するとすると最小性に矛盾することから、条件を満たす$K$のうち最小のものは満たす。
つまり、これが解である。
ソースコード
マクロ等はこちら
LL N;
LL a[55];
LL s;
int main(){
scanf("%lld" , &N);
repp(i,0,N){
scanf("%lld" , a + i);
s += a[i];
}
repm(r,N*(N-1),-1){
LL K = s-r;
if(K < 0) continue;
LL z = 0;
repp(i,0,N){
LL b = (a[i]+K)%(N+1);
if(b == N) z = -1234567;
z += b;
}
if(z == r){
printf("%lld\n" , K);
break;
}
}
return 0;
}解法まとめ
$s - N(N-1) \leq K \leq s$を満たす$K$のうち、$K \geq 0$かつ$b_i = (a_i + K) \% (N+1) \neq N$かつ$\sum{b_i} = s - K = r$を満たす最小のものを求める。(11-24行)