yukicoder : No.1837 Same but Different

なんかしら解くことはできそうだけど、綺麗に解くのは結構難しそう。
https://yukicoder.me/problems/no/1837

問題

整数Nが与えられる。
以下を満たす2つの数列A,Bを1つ構成せよ。

• AとBはいずれも長さNで、各要素は真に単調増加かつ0以上10000以下の整数
• sum(A)=sum(B)
• A[i]+A[j]=B[i]+B[j]となる(i,j)が存在しない。

解法

• N%3=0の場合、A[i]%3=0、B[i]%3=1としておけば絶対にA[i]+A[j]=B[i]+B[j]とはならない。
  • そこで、一旦A[i]=i*3、B[i]=i*3+1としよう。
  • ただ、この場合sum(B)-sum(A)=Nとなるので、Aの後ろの方の要素を適当に3の倍数分増やして帳尻を合わせる。
• N%3!=0の場合、上記手順を取るとsum(B)とsum(A)の差が1か2余る。
  • そこで、A[0]やA[1]をインクリメントし、総和の帳尻を合わせよう。
  • ただ、N%3==2の場合、A[0]=B[0]=1、A[1]=B[1]=4となってしまい条件を満たせない。
  • その場合、B[i]をすべて6ずつ加算しておき、6N分またAの末尾の方に足しこんで帳尻を合わせよう。

int N;
ll A[3030],B[3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int add=0;
	FOR(i,N) {
		A[i]=3*i;
		if(i>=2) A[i]+=6;
		B[i]=3*i+7;
		add+=B[i]-A[i];
	}
	if(N%3) A[0]++;
	if(N%3==2) A[1]++;
	
	A[N]=10002;
	add/=3;
	for(i=N-1;i>=2;i--) {
		x=min(A[i+1]-3,A[i]+add*3);
		add-=(x-A[i])/3;
		A[i]=x;
	}
	
	FOR(i,N) cout<<A[i]<<" ";
	cout<<endl;
	FOR(i,N) cout<<B[i]<<" ";
	cout<<endl;

}

まとめ

こういうのさっと思いつくにはどういう練習をしたらいいんだろう。