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;
  }
};