AtCoder ARC #079 : D - Decrease (Contestant ver.)

時間的には1位になれたのに2WAで逃した。
http://arc079.contest.atcoder.jp/tasks/arc079_b

問題

N要素の数列Aがあったとする。
Aの最大値A[i]がN以上の場合、A[i]をN減らして他を1増やす、という処理を、A[i]の最大値がN未満になるまで処理を繰り返す。

上記処理がちょうどK回になるようなAを求めよ。

解法

最大値とあるがこの処理は別に順番は関係なく、N以上の要素を見つけ次第貪欲に処理を行ってもよい。

さて、最終状態がN=50、A[i]=49になることとして、その前にK回処理を巻き戻すと考えよう。
まずK/N回分全要素について処理を行ったと仮定し、その分処理を巻き戻そう。
あとは先頭からK%N要素について同様に1回分ずつ処理を巻き戻せばよい。

ll K;
int N;
ll V[51];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K;
	
	N=50;
	FOR(i,50) V[i]=49+K/50;
	K%=50;
	
	FOR(i,K) {
		V[i]+=N+1;
		FOR(j,N) V[j]--;
	}
	
	cout<<N<<endl;
	FOR(i,N) _P("%lld%c",V[i],(i==N-1)?'\n':' ');
	
}

まとめ

600ptだしこんなところかな。