読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

TopCoder SRM 577 Div2 Hard EllysCoprimesDiv2

SRM

Div1 Mediumはまだ解けてないので先にDiv2 Hardから。
http://community.topcoder.com/stat?c=problem_statement&pm=12461

問題

整数列が与えられる。
この整数列をソートした後、隣接要素同士が互いに素になるようにしたい。
素にならない場合、間に数値を加えることで素にしていく場合、条件を満たす整数列の最小要素数を答える。

解法

まず数列をソートし、隣接要素を比較する。
隣接要素同士がすでに互いに素なら、間に要素を挿入する必要はない。
素で無いなら、総当たりで間に1個数値を挟んで両者に素となるものを探す。
そのようなものが無い場合、間に2個はさめば確実に隣接要素および挿入した2要素が素になるものがある。

…これで通っちゃったんだけど、間に2個はさめば十分って証明はできなかった。
TopCoder Forumsでも色々議論されてるけど、まだ確定的な証明は出てないな。Editorial待ちか。

class EllysCoprimesDiv2 {
	public:
	int gcd(int a, int b) { return (b==0)?a:gcd(b,a%b);}

	int cop(int A,int B) {
		int i;
		if(gcd(A,B)==1) return 0;
		for(i=A+1;i<B;i++) if(gcd(A,i)==1 && gcd(i,B)==1) return 1;
		return 2;
	}
	
	int getCount(vector <int> numbers) {
		int n=0,i;
		sort(numbers.begin(),numbers.end());
		FOR(i,numbers.size()-1) n+=cop(numbers[i],numbers[i+1]);
		return n;
	}
};

まとめ

間に2個はさめばよい、って直感でやっちゃったけどいいのかなこれ。
他にも同じ人は多かったみたいだけど…。

広告を非表示にする