Euler150

久しぶりのProject Euler

Problem 150

日本語約のWikiだと、
t := 0
for k = 1 up to k = 500500:{
t := (615949*t + 797807) modulo 2^20
sk := t−219
}
と記述されてるが、
sk:=t-219　ではなくて　sk:=t-2^19 です。誰か直すんだ！だれｋ（ｒｙ


とりあえず、int型の1000*1000の配列を用意しようとしたら取り過ぎって怒られた。
int型だと1000*1000すらも取れなかったのか…と目を疑った。
実際に利用する領域数は500000程度だが、これすら確保出来なかったら解けねえｗ
内心かなり不安になりながらvectorで適切に記録したら大丈夫でした。


さて、過去に部分和の問題をやったことがあるのでそれを挙げてみる。
UVa108 http://acm.uva.es/p/v1/108.html
愚直に実装してしまうと、O(n^6)になってしまいTLEになります。
動的計画法で実装すると、O(n^3)で計算出来るようになります。
二次元の部分和計算の基本となる一次元の部分和計算のアルゴリズムはKadane's Algorithmと言うらしい。
一次元だと計算量はO(n)です。


今回のEuler150は動的計画法を利用して計算量O(n^3)で解けます。
それでも計算が終わるまで1分10秒ほどかかってしまうのだけど、枝切り出来る場所あるのかな？

int main()
{
  int t,i,j,d,p,MAX=1000,pd[1000];
  long long ans=1<<30;
  vector< vector<int> > trai(1000);
  
  t=i=j=0;
  d=p=2;
  
  for(int k=1;k<=500500;k++){
    t=(int)((615949LL*t + 797807LL)%(1<<20));
    if(k==d){
      d+=p,p++,i++;
    }
    trai[i].push_back(t-(1<<19));
  }
  
  for(int k=0;k<MAX-1;k++){
    memset(pd,0,sizeof(pd));
    for(int m=0;m<trai[k].size();m++)pd[m]=trai[k][m];
    for(int i=k+1;i<MAX;i++){
      int ind=0,l=0,sum=0;

      for(l=0;!(l&&l%(i-k+1)==0);l++)sum+=trai[i][l];
      pd[ind++]+=sum;
      l--;
      for(;ind<trai[k].size();ind++){
        sum-=trai[i][ind-1];
        sum+=trai[i][l+ind];
        pd[ind]+=sum;
      }
      if(i!=k){
        for(int j=0;j<trai[k].size();j++){
          if(ans>pd[j]){
            ans=pd[j];
          }
        }
      }
    }
  }
  printf("%lld\n",ans);
  return 0;
}

トライアングルをそのままローマ字にしてかつ略して宣言してるとかもうね…痛いｗ
triangle　ちぃ、覚えた。
これで正解数95、あと5つで100に到達