TopCoder SRM 634, Division 2, Level 2 : ShoppingSurveyDiv2

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13458&rd=16077

問題概要

　ある店では 種類の商品を販売している。
　 人の顧客について、それぞれが購入した商品のリストを作成した。なお、各顧客は同じ品物は高々一つしか購入しない。また、全く何も買っていないということも有り得る。その後、各商品について、販売数の合計値を算出した。 番の品物の販売数の合計は である。合計値の算出後、元のリストを紛失してしまった。
　顧客について、全種類の品物を購入した顧客を big shopper と呼ぶとする。顧客の人数 及び、販売数の合計 のみが与えられたとき、big shopper の人数の最小値を求めよ。

解法

　各商品について、その購入者を任意に割り振ることができます。big shopper の数を最小化したいので、全種類買ってしまう顧客が発生しないように割り振ることを考えます。
　題意より、 番の商品を購入しなかった顧客の数は と計算されます。このことから、購入しなかった商品が一種類以上であるような顧客の最大数は です。 からこの値を減じた値が、big shopper の最小数となります。（ 0 を下回る場合があるのでクリッピングが必要）

コード

#define ALL( c ) (c).begin(), (c).end()

class ShoppingSurveyDiv2
{
public:
	int minValue( int N, vector <int> s )
	{
		return max<int>( 0, N - ( N * s.size() - accumulate( ALL( s ), 0 ) ) );
	}
};