Codeforces #276 Div1 B. Maximum Value

シンプルな問題で良い。
http://codeforces.com/contest/484/problem/B

問題

N要素の整数列A[i]が与えられる。
A[p] ＞ A[q]となるような(p,q)の対におけるA[p] mod A[q]の最大値を答えよ。

解法

M(x)を、A[i]に含まれるx以下の最大値とする。これはO(N)で作成可能。

ユニークな各A[p]について、M(A[p]*2-1)、M(A[p]*3-1)、M(A[p]*4-1)…が条件を満たすA[q]の候補なので、M(A[p]*2-1) % A[p]、M(A[p]*3-1) % A[p]、…の最大値を求めればよい。

計算量はかな。

int N;
set<ll> S;
vector<ll> V;
int A[2000005];
int MI[2000005];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>x, A[x]=1;
	for(i=1;i<=2000000;i++) MI[i]=A[i]?i:MI[i-1];
	
	int ma=0;
	FOR(i,1000001) if(A[i]) {
		for(j=2;j*i-1<=2000000;j++) {
			ma=max(ma,MI[j*i-1]%i);
		}
	}
	cout<<ma<<endl;
}

まとめ

終わってみればあっさりだけど、本番うまく書けなかった。