kmjp's blog

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

Codeforces #580 Div1 A. Almost Equal

Cまでに手間取りすぎて微妙だった回。
https://codeforces.com/contest/1205/problem/A

問題

整数Nが与えられる。1~2Nまでの2N個の整数を任意に並べ替えリング状につなげたとする。
そのうちある連結したN個の組に対し、1個だけずれたN個の組を考えたとき、総和の差の絶対値が1以下となるようにできるか。

解法

Nが偶数ならできる。
題意を満たすためには、ちょうど反対側にある要素が1だけ差があるものを配置すればよい。
また、2N回ずらしてもとに戻すことを考えると、同じ方向にずらすと+1,-1と交互にずらすようにすればよい。

int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	if(N%2==0) {
		cout<<"NO"<<endl;
	}
	else {
		vector<int> V;
		for(i=1;i<=N;i++) V.push_back(2*i-(i%2));
		for(i=1;i<=N;i++) V.push_back(2*i-(1-i%2));
		cout<<"YES"<<endl;
		FORR(v,V) cout<<v<<" ";
		
	}
	
	
}

まとめ

まぁ構築問としては簡単な法。