Codeforces #201 Div1. C. Number Transformation II

Cは本番中に解けず。
http://codeforces.com/contest/346/problem/C

問題

N個要素からなる自然数列Xと、非負整数A,B(A>B)が与えられる。

Aに対して、以下のいずれかの処理ができる。

• Aから1を引く
• Aから任意のX[i]についてA % X[i]を引く

AをBにするのに必要な処理数を最小化せよ。

解法

A,Bは10^9と大きいがA-Bは10^6と小さい。
Aから実際に全X[i]に対しA%X[i]を引いてみて、B以上で最小の値になるものを貪欲に選べばよい。
XがN要素あるので、1回探索するとAからN位引くことが期待できる。

また、A%X[i]を引くとB未満になってしまう要素はもう選択することがないのでXから取り除いていけばよい。
全体でO(A-B)で終わる。

int N,A,B;
vector<int> X;

void solve() {
	int f,r,i,j,k,l,x,y,z,tx,ty;
	
	cin>>N;
	FOR(i,N) X.push_back(GETi());
	cin>>A>>B;
	sort(X.begin(),X.end());
	X.erase(unique(X.begin(),X.end()),X.end());
	
	z=0;
	for(;A>B;) {
		y = 1;
		j=X.size();
		for(i=X.size()-1;i>=0;i--) {
			x = A%X[i];
			if(A-x<B) {
				swap(X[i],X[j-1]);
				j--;
			}
			else y=max(x,y);
		}
		X.resize(j);
		A-=y;
		z++;
	}
	
	_P("%d\n",z);
}

まとめ

unorderedなvectorに対して途中の要素を取り除く方法として、最後の要素とswapしてresizeするっての、O(1)でできるのでいいな。