Codeforces #298 Div.2 C: Polycarpus' Dice

いい考察問題だと思う。問題のいわんとすることが理解できれば8割がた解けたといえる気がする。

問題はこちら。

問題

n個のダイスがあり、i番目のダイスは1からd_iの数字を1面ずつ持っている。これらのダイスを振ったところ目の総和がAとなった。各ダイスごとに、他のダイスの目の出方によっては目の総和をAとできないような目がいくつあるかを答えよ。

解法

各ダイスごとに、ほかのダイスがどう出ても目の総和がAとならない目がいくつあるかを数えればいい。つまり、ほかのダイスが最小値をとるときと最大値をとるときについて考えればいい。各ダイスの目の最大値の総和をsとする。

i番目のダイスに注目する。ほかのダイスがすべて1のときを考える。目の総和の最大値 d[i]+(n-1) が A より大きくなる場合は、目の総和がAを越えてしまう目がA-(d[i]+n-1)個ある。

ほかのダイスがすべて最大の目となるときを考える。目の総和の最小値 s-d[i]+1 が A よりも小さくなる場合は、目の総和がAを越えることのできない目が A-(s-d[i]+1)個ある。

２つの値は重複しないのでi番目のダイスで出していけない目の数は２つの値の和である。

n, A = map(int, raw_input().split())
d = map(int, raw_input().split())
s = sum(d)

ans = [0]*n
for i in xrange(n):
    if d[i]+n-1 > A:
        ans[i] += d[i]+n-1-A
    if s-d[i]+1 < A:
        ans[i] += A-(s-d[i]+1)

print " ".join(map(str, ans))

まとめ

考察だけで解ける面白い問題だった。本番は1発で通せたのでよかった。