TopCoder SRM 601 Div2 Medium WinterAndCandies

解いた感じ今回Div2 EasyとDiv2 Mediumはそこまで難易度差が無いような…。
http://community.topcoder.com/stat?c=problem_statement&pm=12859

問題

1～50からなる数列Tが与えられる。同じ数値が複数ある場合もある。
この数列に対してある数値Kを選び、1～Kが１個ずつ含まれるような部分列を作りたい。
条件を満たす部分列は何通りあるか。
なお、２つの部分列は、長さが異なるか、中身が同じでも部分列を構成する元の数値のindexが異なれば別の数列とみなす。

解法

まず、Tに含まれる各要素についてその数をカウントする。
数値iがC[i]回あるとすると、1～Kが含まれる部分列の組み合わせはとなる。
後は各Kについてこの値を計算して合計を取ればよい。

class WinterAndCandies {
	public:
	int getNumber(vector <int> type) {
		int num[51],i;
		int ret=0,ca=1;
		ZERO(num);
		FOR(i,type.size()) num[type[i]]++;
		FOR(i,50) ca*=num[i+1],ret+=ca;
		return ret;
	}
};

まとめ

Div2とはいえMediumにしては簡単な問題。