UTPC2012 : F - Uinny

これは自分で解けなかったので、解説を見て解いてみた。
http://utpc2012.contest.atcoder.jp/tasks/utpc2012_06

簡単なハッシュ計算式が与えられ、同じハッシュ値の文字列を100個生成する。
最初、決定的な手法で同じ文字列を作れるかと思ったけど、文字列長の最大値が50と小さいので無理だった。

このハッシュ値は最大10^9程度。アルファベットが7文字だと26^7≒8*10^9なので、7文字あれば同じハッシュ値の文字列が8つずつある。
また、このハッシュ関数では、ハッシュ値Aの文字列とハッシュ値Bの文字列を合わせた文字列のハッシュ値は、元の２つの文字列にかかわらずそのハッシュ値は一致する。

よって、ランダム探索で同じハッシュ値が2個ある文字列を７組見つけ、その７組から１つずつ文字列を取り出して連結すれば、2^7=128通りの49文字の文字列が作れる。

ll A,B;
map<int, vector<string> > poem;
int nc;
int cand[7];

void solve() {
	int x,y,i,j,rr,TM,nc;
	int tx,ty;
	ll p;
	char str[8];
	

	A=GETi();
	B=GETi();
	poem.clear();
	srand(time(NULL));
	
	
	p=0;nc=0;str[7]=0;
	while(nc<7){
		ll hash=0;
		string st;
		p++;
		FOR(i,7) {
			str[i]='a'+rand()%26;
			hash = (hash*A+(str[i]+1-'a')) % B;
		}
		st = string(str);
		if(poem[(int)hash].size()==0) {
			poem[(int)hash].push_back(st);
		}
		else if(poem[(int)hash].size()==1 &&  poem[(int)hash][0]!=st) {
			poem[(int)hash].push_back(st);
			cand[nc++]=(int)hash;
		}
	}
	
	FOR(i,100) {
		string st="";
		FOR(j,7) st += poem[cand[j]][(i>>j)&1];
		_P("%s\n",st.c_str());
	}
	
	return;
}

まとめ

こんなところでランダム探索が出てきたか…。
誕生日パラドックスはO(√N)程度でハッシュ値が衝突するペアを探せるんだな、覚えておこう。