TopCoder SRM 404 Div1 Medium KSubstring
問題
項数nの数列a[i]を以下のようにして作る。
a[0]=A0
a[i]=(a[i]*X+Y)%M
s(i,k)をa[i]+a[i+1]+……+a[i+k-1]とする。
s(i,k)とs(j,k)の和の範囲が重ならないようなi,jについて、
abs(s(i,k)-s(j,k))の最小値および、最小値をとるときのkを求めよ。
ただし、最小値をとるようなkが複数ある場合、最も大きいkを選べ。
制約条件
M≦10^9
n≦3000
方針
TopCoderには珍しい数列処理っぽい問題(?)
s(i,k)とs(j,k)の和の範囲に重なりがある時、
○○○○◎◎◎◎●●●●●
↑○と◎がs(i,k)の範囲で、◎と●がs(j,k)の範囲
◎の部分をキャンセルさせて、
s(i,k)を○の部分に、s(j,k)を●の部分にとすることができるので、
重なりは無視して列挙してよい。
s(i,k)の値は3000^2=1000万個くらいなので、全列挙してよい。
kごとにs(i,k)をぜんぶのiについて列挙して、
ソートして、隣り合う項のうち、差が最小な部分を見てやればいい。
定数倍の時間がけっこう厳しい。
kがn/2より大きい場合、必ずi,jに重なりが出て、k≦n/2の場合に帰着するので、
k≦n/2以下のkについてだけ調べるようにすると通る。
ソースコード
最悪ケース1.7sくらい。かなりギリギリ
typedef pair<ll,ll> pi; ll a[3000],sum[3000]; pi tmp[3000]; class KSubstring { public: vector <int> maxSubstring(int A0, int X, int Y, int M, int n) { a[0]=A0; rep(i,n-1)a[i+1]=(a[i]*X+Y)%M; rep(i,n)sum[i]=a[i]; ll mn=1ll<<60, mnk=0; for(int k=1;k<=n/2;k++){ int len=n-k+1; rep(i,len)tmp[i]=mp(sum[i],i); sort(tmp,tmp+len); for(int i=0,j=0;i<len;i++){ //値が同じ項が複数あったら、一番離れているもの同士を見る while(j<len-1&&(j<=i||tmp[j].first==tmp[j+1].first))j++; if(j<=i)break; int d=abs(tmp[i].first-tmp[j].first); int a=tmp[i].second, b=tmp[j].second; if(a>b)swap(a,b); //重なりがあったらその部分をキャンセル int kk=a+k<=b?k:b-a; if(d<mn||d==mn&&mnk<kk)mn=d, mnk=kk; } rep(i,len-1)sum[i]+=a[i+k]; } vi ans; ans.pb(mnk); ans.pb(mn); return ans; } };