kmjp's blog

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

AtCoder ARC #055 : D - 隠された等差数列

こういう問題思いつかんなぁ…。
http://arc055.contest.atcoder.jp/tasks/arc055_d

問題

非負整数A,Bに対し初項A,項差Bの等差数列a[i]を考える。
N要素の1桁の整数列d[i]が与えられる。

a[i]のX桁目がd[i]となるようなA,B,Xが存在するなら、最小のAを答えよ。

解法

公式Editorialも参考にしたけど、解説放送に近い解き方をした。
以下数列は0-originで記載する。

対象の桁数Xが増えると考えるとややこしいので、Xが上に増えると考えるのではなく、小数点以下の桁数が下に増えていくと考えるとよい。
そこで以下はX=1と固定する。その分A,Bは小数を許容する。
そのためd[i]=floor(A+i*B)を表現していると考えよう。

数列dの隣接項の差をmod10で考える。すなわち(d[i+1]-d[i])%10を求める。
この差が1通りしかないなら、A=a[0], B=(a[1]-a[0])%10一択であり、そのAを答えればよい。

差が2通りあるなら、その2通りの差は(mod10で)1でなければならない。
これはBの小数部分が項数を重ねるうちに繰り上がって1の位をインクリメントしたケースと考えられる。
小数点以下の足し算で一度に2以上繰り上がることはないので、その場合解が存在しない。

差が2通りある場合小さい方をkとするとBはk≦B<k+1となる実数である。
またd[0]≦A<d[0]+1となる。(Aを10ずつ加算しても1の位は同じd[0]だが、最小のAを求めたいのでその意味はない)

d[i]の値をもとに、a[i]≦A+B*i<a[i]+1となるa[i]をそれぞれ求めよう。
A,Bの詳細はわからないが、floor(A)とfloor(B)はわかってるので、a[i]は1の位がd[i]と一致するようにfloor(B)かfloor(B)+1を加算していけば良い。

このa[i]からA,Bの最適な値を求めたい。
A,Bの範囲はどんな値を取れるか、2次元座標で考えてみる。
a[i]≦A+B*i<a[i]+1より、y=B*x+Aの直線は各線分(i,a[i])-(i,a[i]+1)と交差しなければならない(ただし(i,a[i]+1)は不可)。

これらの線分N個より、Bの範囲が限定できる。
最大値は(i,a[i])-(j,a[j]+1-eps)の最小値だし、最小値は(i,a[i]+1-eps)-(j,a[j])の最大値である。

テストケース2では、たとえば前者は3+eps、後者は3.125....となる。
小数点以下Y桁までで前者をroundup、後者をrounddownした値に際有効な範囲があるなら、その最大値がB。
Y==0の場合、前者のroundupは4、後者のrounddownは3なので解はないが、Y==1なら前者は3.1、後者は3.1なのでB=3.1となる。
Bが定まればa[i]≦A+B*iよりAの最小値も求められる。

Bの範囲を限定するパートは凸包を求め高速化できるが、今回はO(N^2)で(i,j)の対を総当たりしても間に合うようだ。

string D;
int N;
int ND[10101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>D;
	N=D.size();
	FORR(r,D) r-='0';
	
	set<int> difs;
	FOR(i,N-1) difs.insert(D[i+1]-D[i]+((D[i+1]<D[i])?10:0));
	if(difs.size()<=1) return _P("%d\n",D[0]);
	int dif = *difs.begin();
	if(dif==0 && difs.count(9)==1) dif=9;
	
	ND[0]=D[0];
	for(i=1;i<N;i++) {
		x = (D[i]==(D[i-1]+dif+1)%10);
		if(D[i]!=(D[i-1]+dif+x)%10) return _P("-1\n");
		ND[i]=ND[i-1]+dif+x;
	}
	
	double ma_ax=1010;
	double mi_ax=-1;
	FOR(y,N) FOR(x,y) {
		mi_ax=max(mi_ax,(ND[y]-ND[x]-(1.0-1e-9))/(y-x));
		ma_ax=min(ma_ax,(ND[y]-ND[x]+(1.0-1e-9))/(y-x));
	}
	if(mi_ax>ma_ax-1e-10) return _P("-1\n");
	cout<<mi_ax;
	cout<<ma_ax;
	ll p10=1;
	for(;;p10*=10) {
		ll maax_i = floor(ma_ax*p10);
		ll miax_i = ceil(mi_ax*p10);
		cout<<endl;
		cout<<miax_i;
		cout<<maax_i;
		if(miax_i <= maax_i) {
			ll b=0;
			FOR(i,N) b=max(b,ND[i]*p10-maax_i*i);
			cout<<b<<endl;
			return;
		}
	}
	
}

まとめ

最初Xを1つずつ増やしながら似たようなことを整数でやろうとしたけど、そちらでも解けるんかな?