Codeforces #949 : Div2 D. Turtle and Multiplication

不参加だった回。
https://codeforces.com/contest/1981/problem/D

問題

整数Nが与えられる。
以下を満たすN要素の整数列を作れ。

• 各要素は1～3*10^5
• 隣接する整数の積は、すべて異なる
• distinctな要素数が最小

解法

各要素は素数であるとする。
M個の素数が使えるとき、ここから最長何要素の整数列を作れるか考える。
素数に対応するM個の頂点からなるグラフを考える。
ここに、重複した辺を含まない最小のパスを考え、その訪問順に素数を並べればよいことになる。

よって、Nに対し条件を満たす最小のMを求めた後、オイラーツアーの要領でM点の完全グラフから最長のパスを抽出しよう。

int T,N;

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

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;
	}
}

int F(int x) {
	if(x%2==1) return x*(x+1)/2+1;
	else return x*(x+1)/2-(x/2-1)+1;
	
}

template<int MV> class UndirectedEulerPath {
public:
	vector<int> path;
	multiset<int> E[MV];
	void add_path(int x,int y) { E[x].insert(y); E[y].insert(x); }
	int NV=MV;
	void init(int NV_) {
		int i;
		NV=NV_;
		FOR(i,NV) E[i].clear();
		path.clear();
	}
	
	void dfs(int cur) {
		while(E[cur].size()) {
			int tar=*E[cur].begin();
			E[cur].erase(E[cur].begin());
			E[tar].erase(E[tar].find(cur));
			dfs(tar);
		}
		path.push_back(cur);
	}
	
	bool GetPath(int root=-1) { // 開始地点を探し、条件を満たすか判定
		int fo=-1,odd=0,i,np=0;
		FOR(i,NV) {
			np += E[i].size();
			if(E[i].size()%2) odd++, fo=(fo==-1)?i:fo;
		}
		//閉路なら奇数を許容しないようにしておく
		if(odd!=0 && odd!=2) return false;
		if(root==-1) {
			if(odd) {
				root=fo;
			}
			else {
				FOR(i,MV) if(E[i].size()) root=i;
			}
		}
		else {
			if(odd==2&&E[root].size()%2==0) return false;
		}
		dfs(root);
		reverse(path.begin(),path.end());
		return path.size()==np/2+1;
	}
};

UndirectedEulerPath<101000> uep;

void solve() {
	int i,j,k,l,r,x,y; string s;
	cprime();
	
	cin>>T;
	while(T--) {
		cin>>N;
		x=1;
		while(F(x)<N) x++;
		uep.init(x);
		if(x%2==1) {
			FOR(i,x) FOR(j,i+1) uep.add_path(i,j);
		}
		else {
			FOR(i,x) {
				uep.add_path(i,i);
				for(j=i+1;j<x;j++) {
					if(i%2==1&&j==i+1) continue;
					uep.add_path(i,j);
				}
			}
		}
		uep.GetPath();
		FOR(i,N) cout<<prime[uep.path[i]]<<" ";
		cout<<endl;
	}
}

まとめ

わかってしまえばすんなりだけど、気付くのに結構大変かも。