3000ptにしては簡単。
http://codeforces.com/contest/731/problem/F
問題
N個のカードがあり、それぞれA[i]の数値が書かれている。
ここで1枚のリーダーカードを選択し、さらの残りのカードから任意枚数のカードを選ぶことを考える。
この時、後者のカードは数値を任意に減算できる。また、減算後の数値はリーダーカードの倍数でなければならない。
そのようにカードを選んだら、そのカードの数値の総和がプレイヤーのスコアになる。
最適にカードを選んだ場合、スコアは最大いくつになるか。
解法
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に置いたんだろう。