POJ 2452: Sticks Problem

問題

長さがNの同じ要素を含まない数列Sがある.この数列の中で2つの番号i, j (i<j)を選んだ時,その間に含まれる数がSiより大きくSjより小さくなるような連続した部分列のうち最大の長さの物を求めよ.もしそのような部分列が存在しないときには-1を返しなさい.

制約条件

1 <= N <= 50000
1 <= Si <= 1000000

解法

まず単純に考えると,適当に番号iとjを選んで,その間の数がSiとSjの間の数になっているかどうかをbrute forceに調べる方法が考えられます.

ですが,当然ながら計算量はO(N^3)であるため,TLEです.

そこでiを固定して,jをもっと早く求める方法を考えます.もし,[i,N]の中で,最初にiより小さい値の現れる番号xを求めることができるならば,[i,x)の中で最大の大きさを持つ物がjになります.

このような番号xは二分探索で簡単に求めることができます.さらに,[i,x)の間にある数は,あらかじめ数列をデータ構造を使って整理しておけば,速く計算することができます.

ここで「速く」といったのは,どのデータ構造を使うかによって,計算時間が変わるからです.僕は最初,セグメント木で実装をしました.

セグメント木は構築の計算量がO(N)であり,探索の計算量がO(logN)なので,上の方法を使ったとすると,全体の計算量はO(N(logN)^2)です.

これで何とか入るでしょ,と思ってSubmitしたところ,TLEになりました.

この問題は少し探索が行われる回数が多いので,探索がO(1)になるようにSparse Tableを使った実装に変更します.

一応,復習しておくと,セグメント木が空間計算量O(N),構築計算量O(N),探索計算量O(logN)であるのに対して,Sparse Tableは空間計算量がO(NlogN),構築計算量がO(NlogN),探索計算量がO(1)です.

なのでSparse Tableに変更すると全体の計算量がO(NlogN)になります.これでめでたくACできます.


コード

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください