Sliding Window - カメヲラボ

なかなか良さげな問題

http://acm.pku.edu.cn/JudgeOnline/problem?id=2823
巨大な配列(最大10^6)の中で長さkの区間内の最大値と最小値を求める問題。
配列のサイズn=10、区間の長さk=3とすれば、

Window position	Minimum value	Maximum value
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7

このように区切ることになり、最小値・最大値は順に

-1 -3 -3 -3  3  3
 3  3  5  5  6  7

のようになる。配列サイズが大きいので、当然単純なソートでは終わらない。モロにRMQアルゴリズムの問題なのだと思いますが、資料が少ない。っちゅうわけで探しました。最初に見つけたのがodzさんの日記
http://d.hatena.ne.jp/odz/20070319/1174366528
ここから
http://tlas.i.kyushu-u.ac.jp/~bannai/software/misc/
を発見して公開されているコードをそのまま使ってみたわけですが、そのままだと思ったより速くありません(7秒程度)。自分でより単純に書き直したコードの方が少し速い(5秒ちょい)感じです。たぶんコメントアウトされているインラインアセンブリ等でチューニングすれば3〜5秒くらいまでは速くなると思います。しかしstatusを見ると上位は1秒程度というかなりの速度で通っているので、はたしてRMQのチューニングだけでこの速度が出るのか？上位の一人は最速*1であると同時に省メモリでもあるのが非常に興味深い。RMQでなくて、何か素敵なデータ構造と探索アルゴリズムがあるのでしょうか？
とりあえず、普通に書いたコードを載せておきます。

#include<stdio.h>
#include<math.h>

#define MAX(x,y) (x)>(y)?(x):(y)
#define MIN(x,y) (x)<(y)?(x):(y)

int bufMin[2][1000000];
int bufMax[2][1000000];

main() 
{
  int n,i,j,k,r;

  for(;~scanf("%d%d",&n,&k);)
  {
    r=log(1.0*k)/log(2.0);
    // 丸め誤差に気をつけないとダメです。
    // ナニソレという人は下記のトラックバック
    // odzさんの日記をご覧下さい。

    for(i=0;i<n;++i)
    {
      scanf("%d",&bufMin[0][i]);
      bufMax[0][i]=bufMin[0][i];
    }

    for(j=0;j<r;++j)
    {
      for(i=0;i+(1<<j)<n;++i)
      {
        bufMin[j&1^1][i]=MIN(bufMin[j&1][i],bufMin[j&1][i+(1<<j)]);
        bufMax[j&1^1][i]=MAX(bufMax[j&1][i],bufMax[j&1][i+(1<<j)]);
      }
    }
    for(i=0;i<n-k+1;i++)
      printf("%d ", MIN(bufMin[r&1][i],bufMin[r&1][i+k-(1<<r)]));
    puts("");
    
    for(i=0;i<n-k+1;i++)
      printf("%d ", MAX(bufMax[r&1][i],bufMax[r&1][i+k-(1<<r)]));
    puts("");
  }
}

追記

出力で時間かかるんかなーと思って、sprintf+putsにするとGCCでは1秒程速くなりました。でもCだと遅くなっちゃったナァ(;´д｀)GCCの中では上位にきたけど、これはおそらく総合上位の人たちがGCCを使っていないだけでしょう。。。
総合のトップはG++ばっかりです。

追記2

良さげな資料
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

*1:1位ではないけど数回Submitすれば誤差で1位になれると思う