第4回 ドワンゴからの挑戦状 予選 : C - Kill/Death

Dまでは良かったのにね。
https://dwacon2018-prelims.contest.atcoder.jp/tasks/dwacon2018_prelims_c

問題

N人とM人の2つのチームがゲームで対戦する。
両チーム、自身が相手チームをKillした回数が与えられる。

両チーム内のプレイヤーはKill数で降順ソート後、同着のKill数のプレイヤーはDeath数で降順ソートされる。
この時、両チームそれぞれプレイヤーのDeath数の配列としてあり得るものを答えよ。

解法

AチームのKill数総和と同数のDeath数をBチームで割り振ることを考える。
BチームでKill数がkの人数をA(k)人とする。
kill数が同着のa人の間で、Death数b個を降順に並べるやり方をf(a,b)としよう。
f(a,b)はDPで求められる。

あとは各kに対しf(A(k),b)の積を、bの総和が総Death数に一致する範囲で数え上げよう。
こちらもDPで求められる。

BチームのKill数総和と同数のDeath数をAチームで割り振ることを同様に考えて積を取ればよい。

int N,M;
int AS,BS;
map<int,int> A,B;

ll mo=1000000007;

ll memo[1010][1010];
ll pat(int T,int N) {
	if(T<0) return 0;
	if(N==0) return T==0;
	if(T==0) return 1;
	if(memo[T][N]>=0) return memo[T][N];
	
	ll ret=0;
	ret += pat(T-N,N) + pat(T,N-1);
	return memo[T][N]=ret%mo;
}

ll from[1010];
ll to[1010];

ll hoge(map<int,int> M,int T) {
	ZERO(from);
	from[T]=1;
	
	FORR(m,M) {
		int x=m.second;
		ZERO(to);
		
		for(int a=0;a<=T;a++) if(from[a]) {
			for(int b=0;b<=a;b++) {
				(to[a-b]+=from[a]*pat(b,x))%=mo;
			}
		}
		swap(from,to);
		
	}
	return from[0];
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>x, BS+=x, A[x]++;
	FOR(i,M) cin>>x, AS+=x, B[x]++;
	MINUS(memo);
	cout<<hoge(A,AS)*hoge(B,BS)%mo<<endl;
	
}

まとめ

Cにしては若干ややこしいけどFAだった。