TopCoder SRM 839 : Div1 Easy Div2 Hard PerfectParty

久々に割と良い出来。
https://community.topcoder.com/stat?c=problem_statement&pm=17858

問題

整数列Aが与えられる。
この部分列Bを取ったとき、sum(B)が|B|+1で割り切れるような取り方は何通りか。

解法

部分列Bのサイズを総当たりしよう。
あとはAから|B|個の要素を選ぶとき、和を|B|+1で割った余りが0となるケースを、選んだ要素数と総和をキーとし、選び方の個数を値とするDPで求めればよい。

ll dp[55][55];


class PerfectParty {
	public:
	long long invite(vector <int> C) {
		int N=C.size();
		int i;
		ll ret=1;
		int x,y;
		for(i=1;i<=N;i++) {
			ZERO(dp);
			dp[0][0]=1;
			FORR(c,C) {
				for(x=i-1;x>=0;x--) FOR(y,i+1) dp[x+1][(y+c)%(i+1)]+=dp[x][y];
			}
			ret+=dp[i][0];
		}
		return ret;
		
	}
}

まとめ

最初、キャンディーを配るとき自分を入れることに気付かずタイムロスした。