問題は本質的に、とが について隣接していない1 2 ... Nようなの順列を数えることです。ii+11 <= i <= N-1
さらに、プレフィックスの制約があります。で始まる順列のみをカウントする必要がありますpos_1 pos_2 ... pos_k。
前置制約がなければ、OEISの式を使用して O(N) 時間で答えを見つけることができます。それはN大きすぎない場合です。答えの桁数は Θ(N log N) のように増加するため、乗算と加算によって追加のオーバーヘッドが発生します。または、ある数を法として答えを計算することもできます。この質問は、エジプトの情報学オリンピック (2009) で出題されました。
前置制約を使用すると、O(N 2 ) 動的計画法のソリューションが得られます。ただし、N は 16 と小さいため、多項式時間アルゴリズムを使用するのはやり過ぎです。時間 O(2 N N 2 )で実行される、より簡単な動的計画法ソリューションが存在します。このアルゴリズムは、以前のソリューションよりもコーディングに時間がかかる可能性がありますが、考えるのははるかに高速です。ただし、バックトラッキング ソリューションは、最悪の場合、実行に (通常のデスクトップ/ラップトップで) 20 ～ 100 時間かかります。2806878055610N = について訪問するだけの解があります16。それに加えて、解決策のない行き止まりを訪問することで、おそらく多大なコストがかかるでしょう。
O(2 N N 2 ) ソリューション
このソリューションは、グラフ内のハミルトニアン パスの数を見つけるために一般化できます。
私たちの状態はペアになり(S, i)ます。ここで、Sは のサブセットで{1,2...N}あり、iは の要素ですS。のカーディナリティをとしSますM。
で指定された位置F(S,i)に要素を配置する方法の数になるように定義します。とが一緒に表示されないという制約を尊重します。そして要素が位置に配置されます。1, 2, ..., MSkk+1Mi
基本ケースはF(P,pos_k) = 1、すべての時間で O(2 N N 2P = {pos_1, pos_2 ... pos_k}. )を計算するのは簡単です。F(S,i)Si
最終的な答えはF([N],1) + F([N],2) + ... + F([N],N)where[N] = {1,2...N}です。
C++ コードは次のとおりです。のサブセットを表すためにビットマスクが使用されました{1,2...N}。
const int MAXN = 18;
long long DP[1 << MAXN][MAXN];
void solve() {
int n, k;
cin >> n >> k;
int pmask = 0, p;
for(int i = 0; i < k; i++){
cin >> p;
pmask |= (1<<p);
}
// base cases
if(k > 0) {
DP[pmask][p] = 1;
}
else {
for(int i = 0; i < n; i++)
DP[1<<i][i] = 1;
}
long long ans = 0;
for(int bitmask = pmask; bitmask < (1<<n); bitmask++) {
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if((bitmask & (1<<j)) or abs(i-j) == 1)
continue;
DP[bitmask | (1<<j)][j] += DP[bitmask][i];
}
if(bitmask == ((1<<n) - 1))
ans += DP[bitmask][i];
}
}
cout << ans << endl;
}
O(N 2 ) ソリューション
この解決策は、以前にアイデアに出くわしたことがない場合、考えるのが非常に困難です。
まず、接頭辞なしで問題に取り組みましょう。
アイデアは、要素 1、2 .. N を 1 つずつ配置することによって、すべての有効な順列を「構築」することです。
イラストから始めましょう。たとえば、1 2 .. 5 の順列を作成するとします。まず、1 を配置します。1 を配置した後、後の数字で埋められるプレースホルダー要素も挿入します。より正確には、各状態は、プレースホルダーxが空でない要素のシーケンスに置き換えられる順列のクラスです。
1 を挿入した後の順列は、次の 3 つのケースのいずれかのようになります。
1 x- 1 は最初の要素です。プレースホルダーxには、すべての要素 2、3、4、5 が何らかの順序で含まれます。x 1- 1 は最後の要素です。x 1 x- 1 は最初の要素でも最後の要素でもありません。
次に、2 を配置します。これは、前の 3 つのクラスのいずれかのプレースホルダーの 1 つに属している必要があります。
の唯一のプレースホルダーに属しているとし1 xます。2 は 1 に隣接することはできないため、2 を配置した後、それらの間に別のプレースホルダーを挿入する必要があります。これにより、状態が発生し1 x 2ます。さらに、2 が最後の要素ではない場合の順列を考慮する必要があります。state も生成します1 x 2 x。
についてx 1は、同様に状態2 x 1とを作成しますx 2 x 1。
の場合x 1 x、2 を配置するプレースホルダーには 2 つの選択肢があります。前のケースと同様に、状態2 x 1 x、x 2 x 1 x、x 1 x 2、を作成しますx 1 x 2 x。しかし、たとえば、x 2 x 1 x最後のプレースホルダーは他の 2 つのプレースホルダーとは異なることに注意してください。別のバリアを作成する必要なく、3 が発生する可能性があります。これは、プレースホルダーに別の記号を使用して記録します。つまり、代わりにx 2 x 1 oandを使用します。o 1 x 2 x
次に、 に 3 を挿入するとしx 2 x 1 oます。x前のように に3 を配置する場合、バリア プレースホルダーを作成する必要があります。ただし、バリア プレースホルダーとは反対の方向にプレースホルダーを作成するか省略するかを選択できます。プレースホルダーに3 を配置すると、両方向でoプレースホルダーを作成するか省略するかを選択できます。
xさらに、プレースホルダーに慣れていないプレースホルダーも「昇格」する必要がありoます。これは、古いxプレースホルダーが、次の要素である 4 に対して、3 に対して行ったような制約を提供しないためです。
開発パターンの推測はすでに開始できます。一般的なケースでは、i を挿入している間:
まず、i を配置するプレースホルダーを選択する必要があります。
次に、xプレースホルダーに i を配置するとします。バリア プレースホルダーを作成する必要があります。そして、反対方向にプレースホルダーを構築するかどうかを選択できます。
プレースホルダーを使用している場合o、両方向に追加のプレースホルダーを構築する選択肢があります。つまり、全部で 4 つの選択肢があります。
x使用しなかったプレースホルダーをプレースホルダーに更新する必要がありますo。
このアイデアを効率的なアルゴリズムに変える最後の観察は、同じ数の配置された要素と同じ数のプレースホルダーを持つ順列クラスをまとめることができるxoということです。これは、これら 3 つのパラメーターすべてを共有する 2 つの異なるクラスの場合、それらが表す順列の数が等しいためです。
この主張を厳密に証明するには、列挙しているクラスが網羅的で重複していないことを確認するだけで十分です。
プレフィックス
少し考えてみると、接頭辞の問題では、特定の要素 (これを b と呼びます) で始まる順列を数えるだけでよいことがわかります。iとの間の制約の一部はi+1適用できなくなりました。
2 番目の変更は簡単に修正できます。i-1 と i の間の制約が適用できない場合は、i を挿入する前に、すべてのxプレースホルダーをoプレースホルダーに更新します。
最初の変更では、 が配置されるまで、常に先頭にプレースホルダーがあることを確認する必要がありbます。配置bするときは、最初のプレースホルダーに喜んで配置し、その前にプレースホルダーを追加しません。
実装
最初の要素が配置されDP[i][no][nx]たクラスを構築する方法の数を とし、タイプ and のプレースホルダーがそれぞれあります。どの状態でも、プレースホルダーの数は 0 ～ 2 です。したがって、状態空間は O(N^2) です。状態遷移は、前述のとおり一定時間です。inonxoxx
プレフィックス制約なしの問題の O(N) ソリューション
OEIS によると、A n = (n+1)A n-1 - (n-2)A n-2 - (n-5)A n-3 + (n-3)A n-4です。ここで、A niは、とi+1が決して連続しない順列の数です。
O(n) で数列 A nを計算できます。(つまり、合理的に小さい数を法としてA nを計算すると仮定します。)
式の導出は次のとおりです。
補助シーケンスを定義します。
次に、シーケンス A、B、および C の再発を探します。
A nの再発
とが決して隣接しないn有効な順列から要素を削除するとします。の結果の順列は、次の 2 つのケースのいずれかを正確に満たさなければなりません。Pii+1Q1 .. n-1
からの隣接する番号1 ... n-1は で隣接していませんQ。つまり、A n-1Qで説明される順列の 1 つです。
、 、 でちょうど 1 つのペア(i,i+1)が連続して表示されます。つまり、 B n-1 - C n- 1からの順列です。Qi+1 =/= n-1Q
最初のケースでは、要素を正確な位置nに挿入できます。n - 22 つの位置が要素によってブロックされていますn - 1。n2 番目のケースでは、連続する要素間の -の位置の選択肢は 1 つだけです。
A n = (n - 2)A n-1 + B n-1 - C n-1という再帰が得られます。
B nの再発
B n,kkを、とk+1が連続して発生する順列の数とします。合体kさk+1せて 1 つの要素にし、要素の順列Qを考慮してn-1、相対的な順序を維持することができます。
合体した要素の隣にk-1and (元のラベル) が表示されない場合、順列がB n,kに寄与します。これらは、配置と合体した要素内に対応します。その数はA n-1です。k+2(k,k+1)Q2k k+1k+1 kQ
k-1または のいずれかが要素k+2の隣に表示される場合、順列に寄与します。その数はB n-1,k-1 + B n-1,kです。(k,k+1)Q1Q
要素の隣にk-1との両方が表示される場合、順列に寄与します。その数はB n-2,k-1です。k+2(k,k+1)Q1Q
B n , k = 2A n-1 + B n-1,k-1 + B n-1,k + B n-2,k-1 があります。(一部の用語は の場合に消えますk = 1 and k = n-1)。
をまとめると、 B n = 2(n-1)A n-1 + 2B n-1 + B n-2kという再帰が得られます。
C nの反復
C nは単にB n,n - 1です。前の結果から、
C n = 2A n-1 + C n-1 となります。
すべてを一緒に入れて
BとCを消去して、 Aだけで再発するようにする必要があります。練習問題として残します。:-)