Sliding Window（続き） - カメヲラボ

http://d.hatena.ne.jp/Ozy/20070516#p1
の続き

最速は

Range Minimum Query and Lowest Common Ancestor
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
とここからリンクされている資料を参考に数パターン作ってみましたが、実用に耐えうる速度は以下の3つでした。
(1)
前処理をDPで行う方法。前回のエントリで掲載したコードです。DPで前処理を行うのでメモリを使い捨てにするとメモリ制限をオーバーしてしまうのでそれなりに工夫が必要。
(2)
前処理でSegment Treeという一定区間ごとの最小値を保持する2分木を作成しておく方法。なかなか良さそうなのだけどクエリにO(logN)の計算量が必要になるので、今回の問題のようにたくさん出力しなければならない場合は意外に遅い。
(3)
これも前回のに少し触れましたが、対数計算等で前処理に結構時間がかかってしまい(1)と同程度の速度でした。
(4)トータルで相当（後述）
すばらしい(>_<)

(1)〜(3)では、この問題に限って検討すると大体同程度の速度で、メモリ消費はある程度工夫した上で(1)・(2)・(3)の順に少なくなります。実装の手軽さでも(1)・(2)・(3)で、(1)が一番良いかなーと思いました。あとは最速・低消費メモリの(4)なわけですが、これはPKUチャレンジャーのIkkiさんに聞いてみました。

すたっきゅー

まず最速をたたき出すためのアルゴリズムですが、これが素敵過ぎる。結局この問題では、データ構造が命なわけです。区間内の最大値・最小値を出力していくわけですから、ヒープのようなデータ構造があれば理想です。しかし単なるヒープだと、この問題のように区間外になってしまったデータを探すのに結局時間がかかってしまうので、工夫が必要になります。ヒープに近いデータ構造で高速化を図ったのが(2)のSegment Treeで、これは良いアルゴリズムだと思います。
しかし、もっとシンプルで賢いデータ構造がありました。それがすたっきゅー！*1
要するに、区間外になったデータを追い出すためにキューの構造を利用しつつ、キューにデータを追加する前に（キューのtailと）大小の比較を行い、不要なデータを追い出す（stackとして扱いpopしまくる）のです。不要なデータを、そのデータが不要な理由ごとで出口を分けているわけですね。
これだと計算量がO(N)な上に、大小比較しか行っていないので、超高速です。しかも実装がこれまでに挙げた方法よりもずっと単純という。良いことばかりです。うへへ。

最後のチューニング

しかしこのアルゴリズムを使っても大きく速度差がでるわけではありません。ここからさらにコードチューニングが必要です。チューニングと言っても、アルゴリズムがシンプルなので出来ることは入出力処理のみ。入力についてはscanfを使ってもそれほど遅くはありませんが、getcharで一文字ずつ読み込みながら整数への変換を行った方が若干速くなるみたいです（readやgetsでも良いかもしれませんね）。それより出力の方が問題でありまして、printfは数百万回も呼ぶと結構遅いです。printfの代わりにputcharで一文字ずつ出力するか、文字列バッファを用意してgetsかwriteを使って一気に出力するという方法を使うとコードは劇的に速くなります。色々試してみた結果、GCCで最速記録(1076MS)が出たのは入力→getchar・出力→putsでした。

お決まりの超ミジカー（゜д゜）なコード

これは興味のある人だけ解読してみてください

Source

Problem Id:2823  User Id:ozy4dm
Memory:3972K  Time:6388MS
Language:GCC  Result:Accepted

    * Source

v['~~~'],*t,i=-1,*h;
main(s){
  for(t=h=v+'   ';~scanf("%d",v+i++););
  for(t-=i=1;v[-1]/i;*++t=i,i++<*v||printf("%d ",v[*h]))
    for(;h<=t?*h+*v<=i?++h:s*v[*t]>=s*v[i]&&--t:0;);
  ~s&&main(~puts(""));
}

何気にmain再帰^^;

礼仪

非常感谢Ikki
谢谢!

*1:本当は両端キューと言います^^;