Google Code Jam 2014 Round 1B : A. The Repeater

GCJは1Aで抜けたので1Bは練習のみ。
もし参加していたらB-smallの1WAはリトライできるからいいとして、C-largeを落として70ptクリアだったな。
https://code.google.com/codejam/contest/2994486/dashboard#s=p0

問題

N個の文字列が与えられる。
各文字列について以下の処理をコスト１で行える。

• ある文字xを1か所だけ文字xxを複製する。
• 逆に同じ文字が連結している箇所を1文字減らす。

N個の文字列をすべて同じ文字に出来るか。
出来るなら最小コストを答えよ。

解法

まず同じ文字列に出来るか判定する。
これは同じ文字が連結している箇所を全部減らした状態が一致するか判定すればよい。

次に最小コストを求める。
上記処理で連結箇所を全部減らした状態の文字列が生成されるわけだが、この各文字が1～100文字まで連結したとき、各文字列からその状態にするまでのコストを最小になるものを選べばよい。

文字列長をLとするとO(N*L^2)なので時間は余裕。

int N;
string S[101];
string S2[101];
int num[101][101];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	ZERO(num);
	cin>>N;
	FOR(i,N) {
		cin>>S[i];
		S2[i]="";
		FOR(j,S[i].size()) {
			if((j==0 || S[i][j]!=S[i][j-1])) S2[i]+=S[i][j];
			num[i][S2[i].size()-1]++;
		}
	}
	
	FOR(x,N) FOR(y,N) if(S2[x]!=S2[y]) return _P("Case #%d: Fegla Won\n",_loop);
	
	int ret=0;
	FOR(i,S2[0].size()) {
		int mi=100000;
		FOR(j,101) {
			int sum=0;
			FOR(x,N) sum+=abs(num[x][i]-j);
			mi=min(mi,sum);
		}
		ret+=mi;
	}
	
	_P("Case #%d: %d\n",_loop,ret);
}

まとめ

これは割とすんなりとけた。
もっと文字数が多かったら難しかったけど、O(N*L*logL)位にはできるかな？