Ozon Tech Challenge 2020 : F. Kuroni and the Punishment

シンプルな問題設定。
https://codeforces.com/contest/1305/problem/F

問題

N要素の整数列Aが与えられる。
各要素を正の範囲でインクリメントまたはデクリメントを繰り返し、全体のGCDが1より大きくなるようにしたい。
最小で何回インクリメント・デクリメントすればよいか。

解法

まず事前に元数列をランレングス圧縮しておく。
GCDの候補gを乱択することを考える。

まず、全要素偶数にすれば条件を満たすので、解はN以下である。
ということは、2回以上インクリメントまたはデクリメントする要素数は半分以下である。
そこでAから1要素ランダムに選べば、A[i]+1・A[i]・A[i-1]-1のどれかがgの倍数である確率は1/2以上である。

なので、100要素ほどランダムに選び、上記3値の約数をgの候補として探していこう。

int N;
ll A[202020];

const int prime_max = 1000000;
vector<int> prime;
int NP;
int divp[prime_max+1];

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime.push_back(i); NP++;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}
vector<pair<ll,int>> V;
ll mi;
set<ll> D;

void hoge(ll tar) {
	ll sum=0;
	if(tar==1 || D.count(tar)) return;
	D.insert(tar);
	FORR(v,V) {
		ll dif=min(v.first%tar,tar-v.first%tar);
		if(v.first<tar) dif=tar-v.first%tar;
		sum+=dif*v.second;
		if(sum>=mi) return;
	}
	mi=min(mi,sum);
}

void check(ll v) {
	int i;
	FOR(i,NP) {
		if(1LL*prime[i]*prime[i]>v) break;
		if(v%prime[i]==0) {
			hoge(prime[i]);
			while(v%prime[i]==0) v/=prime[i];
		}
	}
	hoge(v);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	FOR(i,N) {
		if(V.empty()||V.back().first!=A[i]) V.push_back({A[i],0});
		V.back().second++;
	}
	cprime();
	mi=N;
	srand(time(NULL));
	FOR(i,100) {
		x=(1LL*rand()*rand()+rand()+i*i)%N;
		check(A[x]);
		check(A[x]+1);
		check(max(1LL,A[x]-1));
	}
	cout<<mi<<endl;
	
}

まとめ

言われれば納得だけど、これ本番で思いつくのしんどいな。