こういう問題思いつかんなぁ…。
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つずつ増やしながら似たようなことを整数でやろうとしたけど、そちらでも解けるんかな?