kmjp's blog

競技プログラミング参加記です

WUPC 2019 : H - Doki Doki Programming Clubs!

その他コンテスト

しょうもないミス。
https://atcoder.jp/contests/wupc2019/tasks/wupc2019_h

問題

２つの数列A,Bがあったとき、その白熱度は
\displaystyle \sum_{i \lt max(|A|,|B|)} (A_{i \% |A|} \times B_{i \% |B|})
とする。

N個の数列P[i]の他、クエリとしてうち２つの数列の対(Xi,Yi)が指定される。
各クエリについて、数列２つの白熱度を答えよ。

解法

基本的には愚直に計算することになるが、同じ計算を繰り返さないようにして処理を軽くしよう。
各数列を、それが現れるクエリにおいてmin(|Xi|,|Yi|)で分類しよう(各数列は複数の分類に登場してもよい)。

あとは分類した長さL毎に、数列Cがあったとすると C'_i = sum_{j \% L = i} C_iを求めておけばよい。
Lの種類は高々O(√(sum(P))程度なのでこれで間に合う。
なお、まったく同じクエリが複数回来ることもあるので、それは別途メモ化しておくこと。

int N,Q;
vector<ll> G[202020];
int X[202020],Y[202020];

set<int> C[202020],ev[202020];
ll ret[202020];
ll mo=1000000007;
vector<ll> cand[202020];
map<pair<int,int>,ll> memo;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		G[i].resize(x);
		cand[i].resize(x);
		FOR(j,x) cin>>G[i][j];
	}
	cin>>Q;
	FOR(i,Q) {
		cin>>X[i]>>Y[i];
		if(X[i]>Y[i]) swap(X[i],Y[i]);
		x=min(G[X[i]].size(),G[Y[i]].size());
		ev[x].insert(i);
		C[x].insert(X[i]);
		C[x].insert(Y[i]);
	}
	
	for(i=1;i<=200000;i++) if(C[i].size()) {
		FORR(c,C[i]) {
			
			FOR(x,i) cand[c][x]=0;
			FOR(x,G[c].size()) cand[c][x%i]+=G[c][x];
			FOR(x,i) cand[c][x]%=mo;
		}
		FORR(e,ev[i]) {
			if(memo.count({X[e],Y[e]})) {
				ret[e]=memo[{X[e],Y[e]}];
			}
			else {
				FOR(j,i) (ret[e]+=cand[X[e]][j]*cand[Y[e]][j])%=mo;
				memo[{X[e],Y[e]}]=ret[e];
			}
		}
	}
	
	FOR(i,Q) cout<<ret[i]<<endl;
}

まとめ

同じクエリが複数回来ることを見落として手間取った。