kmjp's blog

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

Codeforces #298 Div2 C. Polycarpus' Dice

CF#297に参加。
Aから2WAしたりグダグダしてたと思ったら、意外とE,Fの正答率が低く完答者が少ないためDiv2自己ベストの順位が出ました。
http://codeforces.com/contest/534/problem/C

問題

N個のサイコロがあり、各サイコロiは1~D[i]の目を持つ。
N個のサイコロを振った目の合計をSにしたい。
各サイコロについて出ては困る値の数を求めよ。

解法

D[i]の総和をDSとする。
N個のサイコロの目の総和はN~DSの範囲の値を取る。
i番目以外のサイコロでは、(N-1)~(DS-D[i])となる。
よって全体がSになりうるためにはi番目のサイコロは、(S-(DS-D[i]))~(S-(N-1))の間の値なら良い。
そこでそれらを除いたD[i] -( min(D[i],S-(N-1)) - max(1,(S-(DS-D[i])))が答え。

ll N,A;
ll D[303030];
ll tot=0;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A;
	FOR(i,N) cin>>D[i], tot+=D[i];
	FOR(i,N) {
		ll ma=min(A-(N-1) ,D[i]);
		ll mi=max(A-(tot-D[i]),1LL);
		_P("%I64d ",D[i]-(ma-mi+1));
	}
	_P("\n");
}

まとめ

一瞬迷う問題。
これDiv2ならB位でもよさそうだな。