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位でもよさそうだな。