TopCoder SRM 601, Division 2, Level 2 : WinterAndCandies

概要

　いくつかの飴があり、i 番の飴の種類は type[ i ] である。この飴から次の制約を満たすようにいくつかの飴を選びたい。

• 選んだ飴の数を K とする
• 選んだ飴の中に、1, 2, ..., K の種類の飴が全て含まれている

　このときの選び方の総数を求めよ。なお、二つの選び方が異なるとは、少なくとも一つ、片方でだけ選ばれた飴が存在することを言う。

解法

　K が異なるとき背反なので独立に考えることができます。K の最大値は制約より 50 なので、各 K について答えを求めて足し合わせても（よほど遅くなければ）間に合います。
　K が決まったときの選び方は、type が 1 〜 K のものをそれぞれ一つずつ選ぶような選び方です。type が異なるとき独立なので、それぞれの種類の飴の選び方をの数を掛け合わせた値になります。ある種類の飴の選び方は明らかにその種類の飴の数なので、type が 1 〜 K の飴の数を掛け合わせた数が、K が決まったときの選び方の総数です。
　あとは K を全て試して答えを足し合わせれば全体の答えが求まります。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

class WinterAndCandies
{
public:
	int getNumber( vector <int> type )
	{
		const int N = type.size();

		VI counts( 50 );
		FOR( t, type )
		{
			counts[ t - 1 ]++;
		}

		int res = 0;
		REP( i, 0, N )
		{
			int tmp = 1;
			REP( j, 0, i + 1 )
			{
				tmp *= counts[j];
			}
			res += tmp;
		}
		return res;
	}
};