yukicoder : No.469 区間加算と一致検索の問題

★４としてはすんなり。
http://yukicoder.me/problems/no/469

問題

初期状態についてN要素すべて0の数列Xに対し、以下の２種類からなるクエリを順次処理せよ。

• 数列の範囲加算を行う。
• 数列の現在の状態について、過去同じ状態になったことがあればそのタイミングを答える。

解法

何らかの方法で数列をハッシュ化できれば、あとは各ハッシュ値の初出のタイミングを覚えればよい。
自分の場合は素数だけで構成されたN要素の配列Pを作り、X[L]～X[R]にvを加算する場合はハッシュ値にv*sum(P[L...R])を加えるハッシュ計算を行った。
これだと１回の加算に対するハッシュ計算がO(1)で済む。

この問題はハッシュ値を狙って重複させやすいため、ぬるいハッシュを使うと簡単にChallengeされる。
乱数を用いるなど狙い撃ちされないハッシュを使おう。
以下の回答は選ぶ素数を乱数で決めている。

int N,Q;
vector<int> MP;
string S[101010];
int L[101010];
int R[101010];
int V[101010];

const int prime_max = 1000000;
int NP,prime[100000],divp[prime_max];

void cprime() {
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		prime[NP++]=i;
		for(ll j=1LL*i*i;j>i&&j<prime_max;j+=i) divp[j]=i;
	}
}

ll SP[2][202020];
ll mo[2]={1000000007,1000000009};


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	srand(clock());
	FOR(i,201000) {
		SP[0][i+1]=(SP[0][i]+prime[rand()%10000+10000])%mo[0];
		SP[1][i+1]=(SP[1][i]+prime[rand()%20000+20000])%mo[1];
	}
	
	
	MP.push_back(-1);
	cin>>N>>Q;
	FOR(i,Q) {
		cin>>S[i];
		if(S[i]=="!") {
			cin>>L[i]>>R[i]>>V[i];
			MP.push_back(L[i]);
			MP.push_back(R[i]);
		}
	}
	sort(ALL(MP));
	MP.erase(unique(ALL(MP)),MP.end());
	map<pair<ll,ll>,int> memo;
	
	ll v[2]={0,0};
	memo[{v[0],v[1]}]=0;
	FOR(i,Q) {
		if(S[i]=="!") {
			L[i]=lower_bound(ALL(MP),L[i])-MP.begin();
			R[i]=lower_bound(ALL(MP),R[i])-MP.begin();
			FOR(x,2) {
				v[x]+=(SP[x][R[i]]-SP[x][L[i]])*V[i];
				v[x]=(v[x]%mo[x]+mo[x])%mo[x];
			}
			if(memo.count({v[0],v[1]})==0) memo[{v[0],v[1]}]=i+1;
		}
		else {
			cout<<memo[{v[0],v[1]}]<<endl;
		}
		
	}
	
}

まとめ

おそらくぬるめのハッシュを使った解答が結構submitされているので、撃墜祭りしても面白そう？