TopCoder SRM 708 Div1 Easy BalancedStrings

手間取ったけど一応Easy/Medium取れたのでよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=14535

問題

文字列の不安定さ(instability)とは、隣接する文字同士が異なっている箇所の数を示す。
2つの文字列の類似度(similarity)とは、2つの文字列で同じ文字が登場している回数の積の総和とする。

整数Nが与えられる。
以下を満たすN個の文字列集合を答えよ。

• 各文字列は1～100文字のアルファベット小文字からなる。
• N個の文字列の不安定さの合計と、全文字列対の類似度の総和が等しい。

解法

N≦26のときは、それぞれ異なるアルファベット1文字からなる文字列を作れば、不安定さも類似度も0となる。
N＞26の場合、どうやっても類似度が正になってしまう。
不安定さを容易に増やすには、2種類の文字を交互に並べた文字列を作れば、1文字列で不安定さを99増やすことができる。
そこで、N個の文字列の大半を類似度をできるだけ抑えるように構築し、残りの少数の文字列で同数の不安定さを作るようにしよう。

自分は以下のように構築した。

• (N-4)個の文字列は、類似度を増やさないように短い文字列を作る。
  • 具体的には'a'が最大8つ、'b'が最大8つ…としていった。N=100のとき、12種類の文字が8回ずつ登場するので、最大で類似度は12*28=336となる。
• 残り4つの文字列は、それぞれ未使用の文字を2つずつ用い、類似度と同数の不安定さとなるよう文字列を長くしていく。

ほかにもいろいろ解はあるようだ。

class BalancedStrings {
	public:
	vector <string> findAny(int N) {
		vector<string> R;
		int i,x,y,j;
		if(N<=26) {
			FOR(i,N) {
				R.push_back(string(1,'a'+i));
			}
		}
		else {
			int ret=0;
			FOR(i,N-4) {
				R.push_back(string(1,'a'+(i/8)));
				ret += i%8;
			}
			FOR(i,4) {
				int c='a'+18+i*2;
				int d=c+1;
				R.push_back(string(1,c));
				swap(c,d);
				while(ret&&R.back().size()<100) {
					R.back().push_back(c);
					swap(c,d);
					ret--;
				}
			}
			
			
		}
		
		int A=0,B=0;
		FORR(r,R) {
			FOR(i,r.size()-1) if(r[i]!=r[i+1]) A++;
		}
		FOR(j,N) FOR(i,j) {
			FORR(rr,R[i]) FORR(rk,R[j]) if(rr==rk) B++;
		}
		
		if(A!=B || N!=R.size()) cout<<A<<" "<<B<<" "<<N<<" "<<R.size()<<endl;
		
		
		return R;
	}
}

まとめ

最近constructiveな問題多いな。