kmjp's blog

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

yukicoder : No.885 アマリクエリ

これは似たようなテクをTopCoderで見たことあったので。
https://yukicoder.me/problems/no/885

問題

N要素の整数列Aが与えられる。
以下のクエリに順次答えよ。

  • 整数Xが与えられるので、Aの各値をmod Xで置き換える。その都度、Aの総和を答えよ。

解法

Aをmapを使い、値とその登場頻度の対で管理しよう。
各クエリについては、X以上の値を持つものをそれぞれまとめてmod Xの値に置き換え、総和の変分を引いていくとよい。

ここで、P mod QはP/2未満になるので、mod Xでの置き換えは高々O(N*log(max(A)))回しか発生しない。

int N,Q;
map<int,int> M;
ll sum=0;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	FOR(i,N) {
		cin>>x;
		M[x]++;
		sum+=x;
	}
	cin>>Q;
	while(Q--) {
		cin>>x;
		while(M.rbegin()->first>=x) {
			int nx=M.rbegin()->first%x;
			int ny=M.rbegin()->second;
			sum-=(M.rbegin()->first-nx)*1LL*ny;
			M.erase(M.rbegin()->first);
			M[nx]+=ny;
		}
		cout<<sum<<endl;
		
	}
	
}

まとめ

塗り絵に手間取りすぎてここら辺ポイントをロスしてるんだよな。