kmjp's blog

競技プログラミング参加記です

AtCoder ARC #079 : E - Decrease (Judge ver.)

こちらの方がすんなり。
http://arc079.contest.atcoder.jp/tasks/arc079_c

問題

先ほどのDと同じ設定を考える。
http://kmjp.hatenablog.jp/entry/2017/07/29/1000

数列Aが与えられたとき、何回処理を行えるか求めよ。

解法

先の問題と同様、順番は関係ない。
N以上のA[i]を見かけるたび、floor(A[i]/N)回処理を行う、という動作を適当に繰り返すだけでよい。

int N;
ll A[51];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	ll ret=0;
	FOR(x,1000000) {
		FOR(i,N) if(A[i]>=N) {
			ll del=A[i]/N;
			ret += del;
			A[i] -= del*N;
			FOR(j,N) if(i!=j) A[j] += del;
		}
	}
	
	cout<<ret<<endl;
}

まとめ

逆問題で難易度がもうちょっと差が出ると面白かったかも?