TopCoder SRM 759 Div1 Medium Div2 Hard EllysHash

こちらも力技感あるな。
https://community.topcoder.com/stat?c=problem_statement&pm=15435

問題

ある文字列Sのハッシュ値f(S)は以下のように計算できる。

• f("") = 0
• f(S+c) = (f(S)*127 + ord(c)) mod 1000000000000037

同じ文字数の文字列A,B,Cが与えられる。
ここから同じ文字数の文字列Sを作ることを考える。
S[i]はA[i],B[i],C[i]のどれかを任意に選ぶことができる。

f(S)のあり得る最小値を求めよ。

解法

文字数上限が28なので、半分全列挙することを考えよう。
前半14文字からなるハッシュ値と、後半14文字からなるハッシュ値をそれぞれ最大(3^14)通り列挙しよう。
前者を総当たりし、後半の中から和が最小となるものを選べばよい。

これは、後者の値を事前にソートしておけば二分探索で求められる。

ll mo=1000000000000037LL;

ll V[28][3];

class EllysHash {
	public:
	long long getHash(int N, string A, string B, string C) {
		ZERO(V);
		
		int i;
		ll v=1;
		FOR(i,N) {
			V[i][0]=v*A[N-1-i]%mo;
			V[i][1]=v*B[N-1-i]%mo;
			V[i][2]=v*C[N-1-i]%mo;
			v=v*127%mo;
		}
		
		vector<ll> X,Y;
		X.push_back(0);
		Y.push_back(0);
		FOR(i,14) {
			vector<ll> X2,Y2;
			FORR(x,X) {
				X2.push_back((x+V[i][0])%mo);
				X2.push_back((x+V[i][1])%mo);
				X2.push_back((x+V[i][2])%mo);
			}
			FORR(x,Y) {
				Y2.push_back((x+V[i+14][0])%mo);
				Y2.push_back((x+V[i+14][1])%mo);
				Y2.push_back((x+V[i+14][2])%mo);
			}
			swap(X,X2);
			swap(Y,Y2);
		}
		sort(ALL(X));
		sort(ALL(Y));
		ll mi=1LL<<60;
		FORR(x,X) {
			ll di=(mo-x)%mo;
			i=lower_bound(ALL(Y),di)-Y.begin();
			if(i==Y.size()) i=0;
			mi=min(mi,(x+Y[i])%mo);
		}
		return mi;
		
	}
}

まとめ

問題ストックが足りないのかなぁ…？