1

質問へのリンクはUVA-1394: And There Was Oneです。
単純なアルゴリズムは、配列全体をスキャンし、最後に停止する各反復で k 番目の要素をマークすることです。これには O(n^2) 時間がかかります。
私は代替アルゴリズムを検索し、O(N lgN) 時間の解決策として遅延伝播を使用してツリーをセグメント化することを指摘した中国のブログに出くわしました。 セグメント ツリーを調べた後、O(N lgN) 時間のアルゴリズムを作成しようとしましたが、役に立ちませんでした。

私の質問は次のとおり
です。 1. セグメント ツリーを使用して、希望の実行時間を取得できますか?
2. はいの場合、それらの使用方法を教えてください。
3. セグメント ツリーと「zkw」セグメント ツリーは同じですか? - 彼はブログで zkw セグメント ツリーについて言及しています。
更新:上記の問題は Josephus 問題の例です。

4

1 に答える 1

5

  1. はい、できます。

  2. 以下のデータ構造の説明を見ることができます。ここでは、与えられた問題でそれを使用する方法を示します。私たちが表している人口は、明らかに石の輪です。N 個の石すべてが生きている状態から始め、各ステップでツリー内の適切な石を殺します。現在どの要素にいるかを知る必要があるだけです ( mと呼ぶのが適切だと思います)。高レベルのアルゴリズム (詳細はお任せします) は次のとおりです ( Pはデータ構造です)。

    While P.size > 1:
  P.toggle(m) // remove the m-th stone
  m = P.kth(next stone to be killed)

    上記のコードの P.size は、残りのすべての石の数です。以下の説明では、tree[1] に相当します。

    注:データ構造で使用される記号kは、ジャンプ距離を表す問題入力の記号とは異なります。

  3. かなり。その名前は初めて見ましたが、コードは人々が人口ツリーと呼んでいるものと同じように見えます。

    人口ツリーは、セグメント ツリーを使用する簡単な方法です。N 個の要素があり、それぞれに 2 つの可能な状態があります。1 つは生きている状態、0 は死んでいるものです。ツリーは次の 2 つの操作をサポートします。

    • i番号の要素の状態を切り替えます。
    • k 番目(そのインデックスのサイズ) の生きている要素 のインデックスを返します。

    2 番目の操作を明確にするために、生きている要素のセットが {1, 2, 4, 7} であるとしましょう。N = 8 の場合、これは状態配列 01101001 に対応します (要素 0 は無効、要素 1 は有効、要素 3 は有効、など)。

    では、これを実装する方法は？いつものように、ツリーの葉は配列に対応します。つまり、i 番目の要素が生きている場合、i 番目の葉の値は 1 になり、そうでない場合は 0 になります。各内部ノードは、その子の値の合計を記憶しています。

    要素の状態を切り替えるには、対応する葉の値を切り替えてから、その葉からルートへのパスを修正します。

    const int size = 1 << 18; // 2^17 elements, the rest are internal nodes
int tree[size]; // number of living elements in the subtree of a node

void toggle(int i) {
  tree[i + size / 2] ^= 1; // toggle the leaf
  for (i /= 2; i > 0; i /= 2)
    tree[i] = tree[2 * i] + tree[2 * i + 1];
}

    注:ノードにラベルを付ける一般的な方法は、ルートを 1 に等しくし、再帰的にノードnの子を2nと2n+1にすることです。

    k 番目の生きている要素を見つけるには、再帰的に考えることができます: 現在ノードnにいて、そのサブツリーでk 番目の生きている要素を探しています (ノードのサブツリーは、そのノードをルートとするツリーです)。nの左の子2nにk個以上の生きている要素がある場合、 n = 2nに設定します。それ以外の場合は、明らかに適切な子、つまりn = 2n+1に設定されたものに移動します。その場合、サブツリーのk 番目の要素を探す必要はなくなります。左の子のすべての生きている要素をスキップしたため、そのカウントをkから差し引きます。. ここでは、簡単にするために、1 ベースの生きている要素を見ています。

    ここでの基本的な考え方は再帰的かもしれませんが、繰り返し実行することも非常に単純であることを説明が示唆しています。

    int kth(int k) {
  ++k; // because this method looks at elements 1-based
  int current_node = 1; // start at the root
  while (current_node < size / 2) {
    if (tree[2 * current_node] >= k) 
      current_node = 2 * current_node; // descend into the left child
    else {
      k -= tree[2 * current_node]; // fix k
      current_node = 2 * current_node + 1; // descend into the right child
    }
  }
}

    これら 2 つの関数によって、セグメント ツリーが母集団ツリーになります。

これはデータ構造に関する質問だったので、説明されているアイデアはデータ構造を使用しています。ただし、この問題はJosephus 問題として知られており、別の解決策があるので、調べてみてください。

于 2013-01-22T17:42:04.047 に答える