9

2n長さnが約の 2 進数を考えるとしましょう1000。次のプロパティを持つkth数値 (k は によって制限されます) を探しています。10^9

  • の金額は、次のように記述できる1's金額と同じです。0's#(1) = #(0)
  • この番号のすべてのプレフィックスには、0's少なくとも1's. 次の文を否定した後の方が理解しやすいかもしれませ1'sん0's。

そして、基本的にはそれだけです。明確にするために、いくつかの例 n=2をk=2 見てみましょう2n:

0000
0001
0010
0011
0100
0101
0110
0111
1000
and so on...

そして、2ndこれら 2 つの要件を満たす数を見つけなければなりません。つまり0011、 が最初のもので、0101が 2 番目のものです。を変更するk=3と、反対のビットの量が同じ数があるため、答えは存在しませんが、 の場合、0110接頭辞があるため、数値は 2 番目の制約を満たさず、最上位ビット011がすべての数値と同じになります。1

では、アルゴリズムを見つけるためにこれまでに何をしたのでしょうか。

私の最初のアイデアは、可能なすべてのビット設定を生成し、それらの 2 つのプロパティがあるかどうかを確認することでしたが、それらをすべて生成するとO(2^(2n))、n=1000.

0011さらに、 for n=2、000111forなどよりも小さいすべての数値をチェックする必要がないことを認識していn=3ます...率直に言って、最上位ビットの半分が「そのまま」残っているものは、これらの数値が#(1) = #(0)条件を満たす可能性がないためです。それを使えばn半分に減らせますが、あまり役に立ちません。2 * forever の代わりに、アルゴリズムを永久に実行しています。それはまだO(2^n)複雑で、大きすぎます。

アルゴリズムのアイデアはありますか？

結論

このテキストは、Andy Jones の投稿を読んだ後の私の考えの結果として作成されました。

まず第一に、Andy の投稿Kasa 2009の次のドキュメントのポイント 6 であるため、使用したコードは投稿しません。あなたがしなければならないのはnr、私が説明したことをそれと見なすことだけkです。Dyck words アルゴリズムのランクを解除すると、答えをより迅速に見つけることができます。ただし、1 つのボトルネックがあります。

while (k >= C(n-i,j))

それを考慮するとn <= 1000、カタロニア語の数は非常に巨大になる可能性がありC(999,999)ます。いくつかの大きな数の演算を使用できますが、一方で、それを超えて標準の整数を使用するためのちょっとしたトリックを思い付きました。

よりも大きい限り、カタロニア語の数が実際にどのくらい大きいかを知りたくありませんk。そこで、部分和をn x nテーブルにキャッシュするカタロニア語の数字を作成します。

...                                     ...
5 |                              42     ...
4 |                        14    42     ...
3 |                   5    14    28     ...
2 |             2     5     9    14     ...
1 |       1     2     3     4     5     ...
0 | 1     1     1     1     1     1     ...
   ----------------------------------   ...
    0     1     2     3     4     5     ...

それを生成するのは非常に簡単です:

C(x,0) = 1
C(x,y) = C(x,y-1) + C(x-1,y)  where y > 0 && y < x
C(x,y) = C(x,y-1) where x == y

したがって、これだけを見ることができます：

C(x,y) = C(x,y-1) + C(x-1,y)  where y > 0 && y < x

オーバーフローを引き起こす可能性があります。

この時点で停止し、定義を提供しましょう。

k-flow- 整数の実際のオーバーフローではなく、 の値C(x,y)が より大きいという情報ですk。

私の考えは、上記の式を実行するたびに がC(x,y)よりも大きいkか、合計コンポーネントのいずれかが であるかどうかを確認することです-1。-1マーカーとして機能する代わりに配置した場合、それk-flowは起こりました。k-flow数値が任意の正の数値で合計される場合k-flowed、特に 2 つのk-flowed数値の合計が であることは明らかだと思いk-flowedます。

最後に証明しなければならないことは、実際のオーバーフローが発生する可能性がないことです。a + b実際のオーバーフローは、それらのどれではないかを合計した場合にのみ発生する可能性がありますk-flowedが、合計すると、実際のオーバーフローが発生しました。

もちろん、最大値はa + b <= 2 * k <= 2*10^9 <= 2,147,483,647、この不等式の最後の値が符号付きの int の値であると記述できるため、不可能です。また、私の場合のように、int は 32 ビットであると仮定します。

4

2 に答える 2

4

あなたが説明している数字は、Dyck wordsに対応しています。Kasa 2009のパート 2では、それらを辞書順に列挙するための簡単なアルゴリズムが提供されています。さらに読みたい場合は、その参照が役立つはずです。

余談ですが（これを書いているときは半分寝ているので、間違っている可能性があることに注意してください）、ウィキペディアの記事では、長さのダイク語の数は2nカタロニアn語の数であると述べていC(n)ます。探している よりも大きい最小のものを見つけて、nから始まる Dyck 単語を列挙することができます。C(n)kX^n Y^n

于 2013-12-16T03:09:35.220 に答える
0

前回この問題を誤解して申し訳ありませんでしたので、編集しました。修正をお約束します。最初にコードをテストしてください。複雑さは ですO(n^2)。詳細な回答は次のとおりです。

まず、問題を次の問題に等しくすることができます

次のプロパティを持つkth largest数値 (k は によって制限されます) を探しています。10^9

  • の金額は、次のように記述できる1's金額と同じです。0's#(1) = #(0)
  • この数値のすべての接頭辞には、少なくとも [[ 1'sas ]] が含まれている必要があります。つまり、[[ than ]]0'sを含む接頭辞はありません。0's1's

それを説明する例を挙げましょう: letn=3とk=4, 満たされる数の量は です5. 下の図は、前の問題と新しい問題で何を決定する必要があるかを説明しています:

|                       000111  ------>    111000                          ^
|                       001011  ------>    110100                          |
|                       001101  ------>    110010                          |
|  previous 4th number  010011  ------>    101100  new 4th largest number  |
v                       010101  ------>    101010                          |

したがって、新しい問題を解決した後は、ビットごとに not する必要があります。

ここでの主な問題は、新しい問題をどのように解決するかです。まず、A を配列とすると、A[m]{1<=m<=2n}1 または 0 のみが可能でDP[v][q]あり、条件 2 および条件 #(1)=q inを満たす数の量を と{A[2n-v+1]~A[2n]}するDP[2n][n]と、 は満たされる数の量です。

A[1]は 1 または 0 のみです。 の場合A[1]=1、 の数は です。 のDP[2n-1][n-1]場合、 の数は です。 の場合A[1]=0、 の数は1でなければDP[2n-1][n]なりません。の場合、数値は 0 である必要があり、 で判断できます。同じ理論で、比較する数がなくなるまで一つ一つ判断していきます。ここで、理解するための例を挙げることができますkth largestk<=DP[2n-1][n-1]kth largestA[1]A[2]DP[2n-2][n-2]k>DP[2n-1][n-1]kth largestA[1]k=k-DP[2n-1][n-1]A[2]DP[2n-2][n-1]A[j](n=3, k=4)

(動的計画法を使用して DP 行列を決定します。DP 方程式は DP[v][q]=DP[v-1][q-1]+DP[v-1][q] です)

   Intention: we need the number in leftest row can be compared,
              so we add a row on DP's left row, but it's not include by DP matrix
              in the row, all the number is 1.
              the number include by bracket are initialized by ourselves
              the theory of initialize just follow the mean of DP matrix

   DP matrix = (1) (0) (0) (0)                4<=DP[5][2]=5  -->  A[1]=1
               (1) (1) (0) (0)                4>DP[4][1]=3  -->  A[2]=0, k=4-3=1
               (1) (2) (0) (0)                1<=DP[3][1]=3  -->  A[3]=1
               (1) (3)  2  (0)                1<=1  -->  a[4]=1
               (1) (4)  5  (0)                no number to compare, A[5]~A[6]=0
               (1) (5)  9   5                 so the number is 101100

明確に理解していない場合は、コードを使用して理解できます

意図：<code>DP[2n][n] は非常に高速に増加するため、コードn<=19は問題の場合にn<1000ため、大きな数のプログラミングを使用でき、コードはビット操作で最適化できるため、コードはただの参考

/*-------------------------------------------------- 
    Environment: X86 Ubuntu GCC 
    Author: Cong Yu 
    Blog: aimager.com                              
    Mail: funcemail@gmail.com                      
    Build_Date: Mon Dec 16 21:52:49 CST 2013 
    Function: 
--------------------------------------------------*/

#include <stdio.h>

int DP[2000][1000];
// kth is the result
int kth[1000];

void Oper(int n, int k){
    int i,j,h;
    // temp is the compare number
    // jishu is the 
    int temp,jishu=0;

    // initialize
    for(i=1;i<=2*n;i++)
        DP[i-1][0]=i-1;
    for(j=2;j<=n;j++)
        for(i=1;i<=2*j-1;i++)
            DP[i-1][j-1]=0;
    for(i=1;i<=2*n;i++)
        kth[i-1]=0;

    // operate DP matrix with dynamic programming
    for(j=2;j<=n;j++)
        for(i=2*j;i<=2*n;i++)
            DP[i-1][j-1]=DP[i-2][j-2]+DP[i-2][j-1];

    // the main thought
    if(k>DP[2*n-1][n-1])
        printf("nothing\n");
    else{
        i=2*n;
        j=n;
        for(;j>=1;i--,jishu++){
            if(j==1)
                temp=1;
            else
                temp=DP[i-2][j-2];

            if(k<=temp){
                kth[jishu]=1;
                j--;
            }
            else{
                kth[jishu]=0;
                if(j==1)
                    k-=1;
                else
                    k-=DP[i-2][j-2];
            }
        }
        for(i=1;i<=2*n;i++){
            kth[i-1]=1-kth[i-1];
            printf("%d",kth[i-1]);
        }
        printf("\n");
    }
}

int main(){
    int n,k;
    scanf("%d",&n);
    scanf("%d",&k);
    Oper(n,k);
    return 0;
}
于 2013-12-16T03:28:23.470 に答える