Google Code Jam 2014 Round 2 : D. Trie Sharding

こちらも本番はsmallしか解けなかった。
https://code.google.com/codejam/contest/3014486/dashboard#s=p3

問題

M個の文字列S[i]がある。
これらM個の文字列をNグループに分類し、各グループ内の文字列群でTrieを作る。
その時、Trieの総ノード数が最大になるようにしたい。

そのように作ったN個のTrieの総ノード数及び作り方の組み合わせ数を答えよ。

解法

smallはMとNが小さいので、総当たりでMをNグループに分類し、Trieを作ってみればよい。
O(M^N)かかるが十分間に合う。

largeは自力で解けなかったので、他の回答者やTLの内容を参考にした。
M個全部を使ったTrieを考え、各ノードにN個の色を塗ることを考える。
各ノードは複数の色を塗っても良い。
ノードにj番の色が塗られている→j番のグループの文字列群からなるTrieにそのノードが含まれる、と考えると、むしろ各ノードには多数の色を塗れる状況が望ましい。

Trieの各ノードにおいて、そのノードを終端とする文字列S[i]がある場合、文字列S[i]をj番のグループに入れる→始点からそのノードを色jで塗る、と考えられる。
よって各ノードは最大でmin(N,子孫のノードを終端とする文字列数)(以下p)で塗ることができる。
各ノードについてpの総和を取ると、答えの前者(N個のTrieの総ノード数)が得られる。

後者については、ノードをp色で塗る際、そのノードおよびその子ノードにどの色を割り当てるかをDPで解いていけばよい。
ある子ノード以下にx色を塗れるなら、p色中x色を割り当て、結果的に全子ノードでp色を1回ずつ塗る塗り方を求めていく。
この処理は状態として[処理済み子ノード数][割り当て済み色数]を用いたDPで解ける。

class Trie {
public:
	vector<vector<int> > V;
	int find(string s) {
		int cur=0;
		ITR(it,s) if((cur=V[cur][*it])==0) return -1;
		return cur;
	}
	void create(vector<string> S) {
		V.clear();
		V.push_back(vector<int>(256));
		sort(S.begin(),S.end());
		ITR(it,S) {
			int cur=0;
			ITR(c,(*it)) {
				if(V[cur][*c]==0) V.push_back(vector<int>(256)),V[cur][*c]=V.size()-1;
				cur=V[cur][*c];
			}
		}
	}
};

int M,N;
ll mo=1000000007;
const int CN=1001;
ll C[CN][CN];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	vector<string> S;
	string s;
	
	FOR(x,CN) C[x][0]=C[x][x]=1;
	for(i=1;i<CN;i++) for(j=1;j<i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
	
	cin>>M>>N;
	FOR(i,M) cin>>s, S.push_back(s);
	sort(S.begin(),S.end());
	
	Trie tr;
	tr.create(S);
	vector<int> NN=vector<int>(tr.V.size(),0);
	vector<int> str=vector<int>(tr.V.size(),0);
	
	FOR(i,S.size()) str[tr.find(S[i])]++;
	
	ll ret=1;
	int pat=0;
	for(i=tr.V.size()-1;i>=0;i--) {
		vector<int> cand;
		if(str[i]) NN[i]++,cand.push_back(1);
		for(j='A';j<='Z';j++) if(tr.V[i][j]>0) NN[i]+=NN[tr.V[i][j]], cand.push_back(NN[tr.V[i][j]]);
		NN[i]=min(N,NN[i]);
		pat += NN[i];
		
		ll dpdp[101][101];
		ZERO(dpdp);
		dpdp[0][NN[i]]=1;
		FOR(j,cand.size()) {
			FOR(x,NN[i]+1) FOR(y,min(cand[j],x)+1) {
				dpdp[j+1][x-y] += dpdp[j][x]*C[N-x][cand[j]-y]%mo*C[x][y];
				dpdp[j+1][x-y] %= mo;
			}
		}
		ret=ret*dpdp[cand.size()][0]%mo;
	}
	
	_P("Case #%d: %d %lld\n",_loop,pat,ret);
}

まとめ

これは本番思いつかないな…。