Codeforces #1026 : Div2 F. Faculty

ボス問の割にはシンプル。
https://codeforces.com/contest/2110/problem/F

問題

f(x,y) = (x % y) + (y % x)
とする。
整数列Bの美しさとは、f(B[i],B[j])の最大値とする。
整数列Aが与えられるので、そのprefixにおける美しさを答えよ。

解法

数列のprefix A'の末尾に、新たな要素xを加えることを考える。
a=max(A')とすると、f(a,x)は新たな数列A' + [x]の回の候補となる。

• すでにxがA'に含まれる場合、美しさは変化しない。
• x＜aの場合、美しさは変化しない。
• a＜x＜2aの場合、美しさは変化しないが、aの値が更新される
• 2a≦xの場合、A'の全要素yに対し、f(x,y)を再計算しよう。とはいえこれは高々O(log(max(A)))回しか発生しない。

int T,N;
ll A[1<<20];
unordered_set<ll> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		ll ret=0;
		ll ma=0;
		V.clear();
		FOR(i,N) {
			cin>>A[i];
			
			if(ma==0) {
				V.insert(A[i]);
				ma=A[i];
				cout<<ret<<" ";
				continue;
			}
			
			if(V.count(A[i])) {
				cout<<ret<<" ";
				continue;
			}
			
			ret=max(ret,A[i]%ma+ma%A[i]);
			if(A[i]<ma) {
				;
			}
			else if(A[i]<2*ma) {
				ma=A[i];
			}
			else {
				ma=A[i];
				FORR(v,V) ret=max(ret,ma%v+v%ma);
			}
			V.insert(A[i]);
			cout<<ret<<" ";
		}
		cout<<endl;
	}
}

まとめ

まぁまぁの時間で解けて良かった。