TopCoder SRM 634 Div1 Easy ShoppingSurveyDiv1、Div2 Medium ShoppingSurveyDiv2

SRM634に参加。Mediumをまた落としてしまい、Easyもいまいちな速度のためレート変更はほとんどなし。
http://community.topcoder.com/stat?c=problem_statement&pm=13455
http://community.topcoder.com/stat?c=problem_statement&pm=13458

問題

N人の人がM種類の商品を買う。
各人は１種類当たり１個までしか買うことができない。

各商品を買った人の数はS[i]である。

• Div1 Easy: K個以上の商品を買った人のことをbig shopperと呼ぶ
• Div2 Medium: 全商品を買った人のことをbig shopperと呼ぶ

条件S[i]を満たす最小のbig shopperの数を答えよ。

解法

Div2 MediumはDiv1 EasyのうちK=Mの場合である。
よって今後はDiv1 Easyについて回答する。

big shopper数を少ない順に総当たりして、条件を満たすか調べればよい。
まず、K個以上買った人がbig shopperになるので、どうせbig shopperになるならその人は全商品を買うのが良い。
よって、big shopper数をpと仮置きした場合、S[i]からそれぞれpを引き、残ったS[i]を残った(N-p)人が(K-1)個以下の購入で賄いきれればok。

なお、S[i]からp引いたものを(N-p)で賄う判定は、単純にsum(S[i])≦(N-p)*(K-1)を判定すればよく、S[i]を大きい順から引いて…といった処理は不要である。

class ShoppingSurveyDiv1 {
	public:
	int minValue(int N, int K, vector <int> s) {
		int i,j;
		FOR(i,N+1) {
			int left=0;
			FOR(j,s.size()) if(s[j]>i) left+=s[j]-i;
			if(left<=(N-i)*(K-1)) break;
		}
		return i;
	}
}

class ShoppingSurveyDiv2 {
	public:
	int minValue(int N, vector <int> s) {
		int i,j;
		FOR(i,N+1) {
			int left=0;
			FOR(j,s.size()) if(s[j]>i) left+=s[j]-i;
			if(left<=(N-i)*(s.size()-1)) break;
		}
		return i;
	}
}

まとめ

まじめに「残ったS[i]をうまい順で引いて…」なんてことやったせいで時間食った。