AtCoder ARC #145 : D - Non Arithmetic Progression Set

パズルっぽい問題。
https://atcoder.jp/contests/arc145/tasks/arc145_d

問題

整数N,Mが与えられる。
以下を満たす整数集合Sを1つ構築せよ。

• N個の異なる整数からなる
• 和はMである
• 3要素が等差数列を成さない。すなわち、3値(x,y,z)を取ると、y-x!=z-yである。

解法

Sに、三進数で01だけで構成される値を入れれば3つ目の条件を満たせる。
y-x=z-yであるにはx+z=2yでなければならないが、x!=zならx+zの三進数表記に1が現れ、これは2yの形で表現できないためである。

そのためSにそのような値をN個適当に入れよう。
S全体をインクリメント/デクリメントしてもy-x!=z-yの判定結果は変わらないので、Sの総和がMに近づくよう全体を増減する。
あとはSの総和がMから少しずれるが、余った分をSの最小値に加減算して調整してしまってよい。

int N;
ll M;
ll A[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<ll> B={1};
	FOR(i,15) B.push_back(B.back()*3-1);
	
	cin>>N>>M;
	int ma=0,id=0;
	for(i=1;i<N;i++) {
		x=i-1,y=0;
		if(x==0) x=1<<14;
		while(x%2==0) x/=2,y++;
		if(y>ma) ma=y,id=i;
		A[i]=A[i-1]+B[y];
		M-=A[i];
	}
	FOR(i,N) A[i]+=M/N;


	M-=N*(M/N);
	if(M>0) {
		FOR(i,N) A[i]++;
		M-=N;
	}
	A[0]+=M;
	
	FOR(i,N) cout<<A[i]<<" ";
	cout<<endl;
	
}

まとめ

これ本番中にできる気しないな…。