CF 534C. Polycarpus' Dice

問題

http://codeforces.com/problemset/problem/534/C
n個のサイコロがあってサイコロiの目は1〜diのいずれかが出る。
このn個のサイコロをふって出た目の総和がAだとする。
このとき、各iに対して「サイコロiの出た目の数としてあり得ない目の数」の種類数を求める問題。
例えば、普通の6面のサイコロを2個ふってその目の和が8だったら、どちらのサイコロも1の目が出ることはあり得ないため、答えは{1,1}となる。

解法

各サイコロiに対してその目の出うる目の数の下限と上限を考える。
「サイコロiがxを出して他のサイコロが全部本気出してもAには届かないよなぁ」
というxのうち最大のもの+1が下限で、これをx1
「サイコロiが本気出してyの目が出たとき他のサイコロが全部1の目になってもAより大きいなぁ」
というyのうち最小のもの-1が上限(の候補の一つ)で、これをy1
とおくと、
サイコロiのでうる目の値は
[max(1,x1) , min(y1,di)]
となる。あとはdiからこの区間内の整数の個数を引けば良い。

ただしn=1の時はA=出たサイコロの目のはずなので、di-1を出力すれば良い。