yukicoder : No.2719 Equal Inner Products in Permutation

こういうのどうやって思いつくんだろうな。
https://yukicoder.me/problems/no/2719

問題

正整数Nが与えられる。
以下を満たす長さNの数列A,B,Cを構築せよ。

• 1～3Nが1回ずつ登場する
• AとBの積和と、BとCの積和が一致する

解法

• N=1の時は解なし
• N=2,3,4の時は総当たりなどで解を出せる。
• Nの解があったとき、N+3の解を構築することを考える。
  • Aに(3N+1,3N+2,3N+9)、Bに(3N+6,3N+8,3N+7)、Cに(3N+3,3N+4,3N+5)を追加すると、やはりこの時もAとBの積和はBとCの積和に等しい。

このことからN=2以上の時は常に解を構築可能。

int N;
vector<int> P[3];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	if(N==1) {
		cout<<-1<<endl;
		return;
	}
	
	if(N%3==2) {
		P[0]={1,4};
		P[1]={3,6};
		P[2]={5,2};
	}
	else if(N%3==0) {
		P[0]={1,2,9};
		P[1]={6,8,7};
		P[2]={3,4,5};
	}
	else {
		P[0]={1,2,4,11};
		P[1]={7,9,10,12};
		P[2]={8,5,6,3};
	}
	
	x=P[0].size();
	while(x<N) {
		P[0].push_back(3*x+1);
		P[0].push_back(3*x+2);
		P[0].push_back(3*x+9);
		P[1].push_back(3*x+6);
		P[1].push_back(3*x+8);
		P[1].push_back(3*x+7);
		P[2].push_back(3*x+3);
		P[2].push_back(3*x+4);
		P[2].push_back(3*x+5);
		x+=3;
	}
	
	FOR(i,3) FORR(a,P[i]) cout<<a<<" ";
	cout<<endl;
	
}

まとめ

これ先にこの性質知ってて問題作ったのかな？