Codeforces #376 Div2 F. Video Cards

3000ptにしては簡単。
http://codeforces.com/contest/731/problem/F

問題

N個のカードがあり、それぞれA[i]の数値が書かれている。
ここで１枚のリーダーカードを選択し、さらの残りのカードから任意枚数のカードを選ぶことを考える。
この時、後者のカードは数値を任意に減算できる。また、減算後の数値はリーダーカードの倍数でなければならない。
そのようにカードを選んだら、そのカードの数値の総和がプレイヤーのスコアになる。

最適にカードを選んだ場合、スコアは最大いくつになるか。

解法

A[i]は正なので、全カードを選ぶのが最適なのは明らかである。
また、リーダーカードA[i]に合わせて他のカードの数値A[j]を減算する場合、減算後の数値はA[i]の倍数のうちA[j]以下の最大値であるのがいいのは明らかである。
よって、あとは各カードをリーダーカードにした際のスコアを求めてみて最大値を取ればよい。

S[x] := スコアがxのカードの枚数
T[l,r] := sum(S[l...r])とする。

s=A[i]であるカードをリーダーカードにした場合、スコアはT[s...(2s-1)]*s + T[2s...(3s-1)]*2s + T[3s...(4s-1)]*3s + ...となる。
sが小さいとこの総和をO(N)回取ることになりTLEするが、sが同じ複数のカードはどれをリーダーカードにしてもスコアが同じはずなので、異なるsに対してのみ前述の総和を取るようにすればTLEしない。

int N;
int A[202020];
ll S[402030];
set<int> SS;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		S[A[i]]++;
		SS.insert(A[i]);
	}
	FOR(i,402020) S[i+1]+=S[i];
	
	ll ma=0;
	FORR(r,SS) {
		ll t=0;
		for(x=r;x<=200000;x+=r) t += (S[x+r-1]-S[x-1])*x;
		ma=max(ma,t);
	}
	cout<<ma<<endl;
	
	
}

まとめ

なんでこれFに置いたんだろう。