最小MセグメントとO(nlogn)高速アルゴリズム
4196 ワード
まず、このアルゴリズムはまだ出ていません.
『数列分割』解題報告
〔件名の説明〕
長さNの整数数列(N≦15000)を与え、最小のMを求めることが要求され、各数列を適切なK部に分割するスキーム(各部は数列上に連続したセグメントであり、空ではない)が存在し、各部の数字の和はM以下である.
〔アルゴリズム解析〕
この問題はまた典型的な「最大値をできるだけ小さくする必要がある」形式であり、このような問題に対しては、二分ベースのアルゴリズムを用いて解決することが多い.この問題に対しては,二分列挙Mの値であり,このMに対して分割スキームが存在するか否かを判断し,範囲を縮小する.
この問題の難易度は、数列に負の数が存在する可能性があることであり、数列の1つの接頭辞の数とMより大きい場合、より後の接頭辞とMより小さい可能性がある(負の数のため).また、特定のMについては、数列にK−1部に分割されたものがあれば、K部に分割されたものは必ずしも存在しない.例えば、数列−1−2、M＝−2については、2部に分割されたものが存在するが、3部に分割されたものは存在しない.これにより、一般的な簡単なアルゴリズムは適用されなくなります.
有効なアルゴリズムが見つからない場合は、まず素朴なアルゴリズムを見てみましょう.「1部あたりの数字とM以下の分割スキームが適切に存在するかどうか」という問題に対して、このような動的計画アルゴリズムを容易に設計することができる.
S[i]は、原数列の前のi個の数からなるサブシーケンスを表し、Sum[i]は、S[i]のすべての数字の和を表す.f[i][j]を定義することは、S[i]を適切なj部に分割するスキームが存在するか否かを示し、各部の数字の和はM以下であり、f[i][j]はtrueまたはfalseである.
j=0の場合、f[i][j]は、i=0の場合のみtrueであり、残りはfalseである.
i=0の場合、f[i][j]は、j=0の場合のみtrueであり、残りはfalseである.
j>0かつi>0の場合、f[i][j]=f[i 1][j-1]or f[i 2][j-1]or...or f[il][j-1]であり、ixは［0,i-1］の範囲内であり、Sum[i]-Sum[ix]≦Mを満たすすべての整数である.
このアルゴリズムの時間的複雑度はO(N 3)に達し,本題のデータ範囲には耐えられない.しかし,このモデルでは状態形式が単純(ブール型)であり,転移方程式も比較的特殊であり,いくつかの内在的な法則が存在する可能性があることが容易に分かった.では、このダイナミックプランニングモデルを深く研究します.
転移方程式の第1の特殊な点は,同じiの異なるjに対して,方程式中のi 1...ilの値が同じであることである.
処理されているのはi=7行で、この行の各格子(状態)について、その値は前の行と同色の格子の値からor演算され、遷移方程式の特殊な形式のため、上図のような形態となっている.各行を1つのブールベクトルと見なすと、i行目を計算するのは、実際にはi 1...ilを見つけてから、このl個のベクトルを加算し(ここではor演算)、右に1ビットシフトし、最高位は捨て(実際にはfalse)、最低位は0を補うことで、i番目のベクトルが得られる.
しかし,この認識はアルゴリズムの時間的複雑さを低減するのにしばらく役立たず,より多くのものが必要である.移行方程式に戻り、i 1...ilという集合を観察すると、散乱しているように見えますが、そうではありません.ixであり、Sum[i]-Sum[ix]≦Mの集合、すなわちSum[i]-M≦Sum[ix]です.0～i-1行をSum値の大きい順から小さい順に並べ替えると、i 1...ilに対応するのは実際には前のl行です.
このようにi行目に進むと、0〜i−1行において2分探索を用いて遷移に係る行を探し出し、それらorを立ち上がり、右シフトしてi行目の結果を得、さらにi行目を適切な位置に挿入し、0〜i行をSum降順に配列させることができる.
上記の説明では、1つの位置を二分して検索し、要素(ブールベクトル)を空の位置に挿入し、ある位置の前にすべてのベクトルorが起きる値を求める操作について説明します.これは典型的には離散化＋ツリー配列を用いて解決できる問題であるが,操作の要素がベクトルであるため,基本操作にはO(N)の代価があり,アルゴリズムの時間的複雑度はO(N 2 log N),空間的複雑度はO(N 2)となり,本題のデータパターンには耐えられない.
前のアルゴリズム解析に戻って、i行目に対して、その値は前の連続するl行orによって再び変位して得られ、得られた値と前のl行を再びorすると、1つのベクトルを右に1つの単位を変位して自分のorと起きることに相当し、ベクトルの中のtrueはより「ばらばら」にならず、より「連続」になる可能性があると直感的に感じられる.特に,このベクトル内のtrueが本来連続するセグメントであれば,右変位再orの結果は依然として連続する.また,最初の行は連続的(trueが1つしかない)であり,数学的帰納法を用いていくつかのものを得ることができることを示唆した.少し解析すると,アルゴリズムの任意の時点で,任意の1つのベクトルの中のtrueが連続しており,Sum値で並べ替えた後に前の任意の複数の連続ベクトルorが起きた結果のtrueも連続していることが分かる.
この結論から,整数対を用いてベクトルを記述することができる:(X,Y)はベクトルの中でXからYまでのセグメントがtrueであることを表す.or演算も変位演算も簡単に実現できます.
(X1,Y1)or(X2,Y2)＝(min(X1,X2),max(Y1,Y2))
(X,Y)>>1＝(X＋1,Y＋1)
このような表現法を前のアルゴリズムに用いると,時間的複雑度O(N log N),空間的複雑度O(N)の実行可能なアルゴリズムが得られる.
〔まとめ〕
このような複雑度の低いアルゴリズムの鍵は,各ベクトルのtrueが連続しており,上記の文脈から飛び出して数学的命題が得られることにある.
1つの数列をM以下の数の和に分割することが要求され、A部とB部に分割するスキームが同時に存在する場合、［A,B］の各数に分割するスキームも存在する.
上記では実際にこの結論を実証したが,素朴な動的計画アルゴリズムによってブリッジされた.恥ずかしいことに、私は純粋な数学のツールを使って証明する方法を見つけていません.皆さんが教えてくれることを望んでいます.
xqzが提供してくれたプログラムに感謝します.
{$inline on} program xqz; const maxn=20005; oo=1 shl 30; var i,j,k,m,n,ll,rr,mid,t,k1,k2:longint; a,s,c1,c2,f,g:array[0..maxn] of longint; procedure sort(ll,rr:longint); var i,j:longint; begin i:=ll; j:=rr; t:=a[random(rr-ll+1)+ll]; while i<=j do begin while a[i]>t do inc(i); while a[j]ll then sort(ll,j); if i=x then ll:=mid else rr:=mid-1; end; get:=ll; end; procedure find(i:longint); begin while i>0 do begin if c1[i]k2 then k2:=c2[i]; i:=i-i and(-i); end; end; procedure add(i,k:longint); begin while i<=n+1 do begin if f[k]c2[i] then c2[i]:=g[k]; i:=i+i and(-i); end; end; begin assign(input,'candy.in'); reset(input); assign(output,'candy.out'); rewrite(output); read(n,m); for i:=1 to n do begin read(s[i]); if s[i]>0 then rr:=rr+s[i] else ll:=ll+s[i]; s[i]:=s[i-1]+s[i]; a[i]:=s[i]; end; a[n+1]:=0; sort(1,n+1); a[0]:=oo; while ll-1 then inc(k2); f[i]:=k1; g[i]:=k2; add(get(s[i]),i); end; if (f[n]<=m)and(g[n]>=m) then rr:=mid else ll:=mid+1; end; writeln(ll); close(input); close(output); end.
すぐに自分で打って出して、こんなブスなプログラムは見せないから...
『数列分割』解題報告
〔件名の説明〕
長さNの整数数列(N≦15000)を与え、最小のMを求めることが要求され、各数列を適切なK部に分割するスキーム(各部は数列上に連続したセグメントであり、空ではない)が存在し、各部の数字の和はM以下である.
：Viet Nam Olympiad in Informatic 2005, Day I〔アルゴリズム解析〕
この問題はまた典型的な「最大値をできるだけ小さくする必要がある」形式であり、このような問題に対しては、二分ベースのアルゴリズムを用いて解決することが多い.この問題に対しては,二分列挙Mの値であり,このMに対して分割スキームが存在するか否かを判断し,範囲を縮小する.
この問題の難易度は、数列に負の数が存在する可能性があることであり、数列の1つの接頭辞の数とMより大きい場合、より後の接頭辞とMより小さい可能性がある(負の数のため).また、特定のMについては、数列にK−1部に分割されたものがあれば、K部に分割されたものは必ずしも存在しない.例えば、数列−1−2、M＝−2については、2部に分割されたものが存在するが、3部に分割されたものは存在しない.これにより、一般的な簡単なアルゴリズムは適用されなくなります.
有効なアルゴリズムが見つからない場合は、まず素朴なアルゴリズムを見てみましょう.「1部あたりの数字とM以下の分割スキームが適切に存在するかどうか」という問題に対して、このような動的計画アルゴリズムを容易に設計することができる.
S[i]は、原数列の前のi個の数からなるサブシーケンスを表し、Sum[i]は、S[i]のすべての数字の和を表す.f[i][j]を定義することは、S[i]を適切なj部に分割するスキームが存在するか否かを示し、各部の数字の和はM以下であり、f[i][j]はtrueまたはfalseである.
j=0の場合、f[i][j]は、i=0の場合のみtrueであり、残りはfalseである.
i=0の場合、f[i][j]は、j=0の場合のみtrueであり、残りはfalseである.
j>0かつi>0の場合、f[i][j]=f[i 1][j-1]or f[i 2][j-1]or...or f[il][j-1]であり、ixは［0,i-1］の範囲内であり、Sum[i]-Sum[ix]≦Mを満たすすべての整数である.
このアルゴリズムの時間的複雑度はO(N 3)に達し,本題のデータ範囲には耐えられない.しかし,このモデルでは状態形式が単純(ブール型)であり,転移方程式も比較的特殊であり,いくつかの内在的な法則が存在する可能性があることが容易に分かった.では、このダイナミックプランニングモデルを深く研究します.
転移方程式の第1の特殊な点は,同じiの異なるjに対して,方程式中のi 1...ilの値が同じであることである.
処理されているのはi=7行で、この行の各格子(状態)について、その値は前の行と同色の格子の値からor演算され、遷移方程式の特殊な形式のため、上図のような形態となっている.各行を1つのブールベクトルと見なすと、i行目を計算するのは、実際にはi 1...ilを見つけてから、このl個のベクトルを加算し(ここではor演算)、右に1ビットシフトし、最高位は捨て(実際にはfalse)、最低位は0を補うことで、i番目のベクトルが得られる.
しかし,この認識はアルゴリズムの時間的複雑さを低減するのにしばらく役立たず,より多くのものが必要である.移行方程式に戻り、i 1...ilという集合を観察すると、散乱しているように見えますが、そうではありません.ixであり、Sum[i]-Sum[ix]≦Mの集合、すなわちSum[i]-M≦Sum[ix]です.0～i-1行をSum値の大きい順から小さい順に並べ替えると、i 1...ilに対応するのは実際には前のl行です.
このようにi行目に進むと、0〜i−1行において2分探索を用いて遷移に係る行を探し出し、それらorを立ち上がり、右シフトしてi行目の結果を得、さらにi行目を適切な位置に挿入し、0〜i行をSum降順に配列させることができる.
上記の説明では、1つの位置を二分して検索し、要素(ブールベクトル)を空の位置に挿入し、ある位置の前にすべてのベクトルorが起きる値を求める操作について説明します.これは典型的には離散化＋ツリー配列を用いて解決できる問題であるが,操作の要素がベクトルであるため,基本操作にはO(N)の代価があり,アルゴリズムの時間的複雑度はO(N 2 log N),空間的複雑度はO(N 2)となり,本題のデータパターンには耐えられない.
前のアルゴリズム解析に戻って、i行目に対して、その値は前の連続するl行orによって再び変位して得られ、得られた値と前のl行を再びorすると、1つのベクトルを右に1つの単位を変位して自分のorと起きることに相当し、ベクトルの中のtrueはより「ばらばら」にならず、より「連続」になる可能性があると直感的に感じられる.特に,このベクトル内のtrueが本来連続するセグメントであれば,右変位再orの結果は依然として連続する.また,最初の行は連続的(trueが1つしかない)であり,数学的帰納法を用いていくつかのものを得ることができることを示唆した.少し解析すると,アルゴリズムの任意の時点で,任意の1つのベクトルの中のtrueが連続しており,Sum値で並べ替えた後に前の任意の複数の連続ベクトルorが起きた結果のtrueも連続していることが分かる.
この結論から,整数対を用いてベクトルを記述することができる:(X,Y)はベクトルの中でXからYまでのセグメントがtrueであることを表す.or演算も変位演算も簡単に実現できます.
(X1,Y1)or(X2,Y2)＝(min(X1,X2),max(Y1,Y2))
(X,Y)>>1＝(X＋1,Y＋1)
このような表現法を前のアルゴリズムに用いると,時間的複雑度O(N log N),空間的複雑度O(N)の実行可能なアルゴリズムが得られる.
〔まとめ〕
このような複雑度の低いアルゴリズムの鍵は,各ベクトルのtrueが連続しており,上記の文脈から飛び出して数学的命題が得られることにある.
1つの数列をM以下の数の和に分割することが要求され、A部とB部に分割するスキームが同時に存在する場合、［A,B］の各数に分割するスキームも存在する.
上記では実際にこの結論を実証したが,素朴な動的計画アルゴリズムによってブリッジされた.恥ずかしいことに、私は純粋な数学のツールを使って証明する方法を見つけていません.皆さんが教えてくれることを望んでいます.
xqzが提供してくれたプログラムに感謝します.
{$inline on} program xqz; const maxn=20005; oo=1 shl 30; var i,j,k,m,n,ll,rr,mid,t,k1,k2:longint; a,s,c1,c2,f,g:array[0..maxn] of longint; procedure sort(ll,rr:longint); var i,j:longint; begin i:=ll; j:=rr; t:=a[random(rr-ll+1)+ll]; while i<=j do begin while a[i]>t do inc(i); while a[j]ll then sort(ll,j); if i=x then ll:=mid else rr:=mid-1; end; get:=ll; end; procedure find(i:longint); begin while i>0 do begin if c1[i]k2 then k2:=c2[i]; i:=i-i and(-i); end; end; procedure add(i,k:longint); begin while i<=n+1 do begin if f[k]c2[i] then c2[i]:=g[k]; i:=i+i and(-i); end; end; begin assign(input,'candy.in'); reset(input); assign(output,'candy.out'); rewrite(output); read(n,m); for i:=1 to n do begin read(s[i]); if s[i]>0 then rr:=rr+s[i] else ll:=ll+s[i]; s[i]:=s[i-1]+s[i]; a[i]:=s[i]; end; a[n+1]:=0; sort(1,n+1); a[0]:=oo; while ll-1 then inc(k2); f[i]:=k1; g[i]:=k2; add(get(s[i]),i); end; if (f[n]<=m)and(g[n]>=m) then rr:=mid else ll:=mid+1; end; writeln(ll); close(input); close(output); end.
すぐに自分で打って出して、こんなブスなプログラムは見せないから...