3

http://www.spoj.com/problems/CTRICK/ spojの問題です

マジシャンはカードの小さなパックをシャッフルし、それを裏向きにして、次の手順を実行します。

  1. 一番上のカードがパックの一番下に移動します。新しいトップカードが表向きにテーブルに配られます。スペードのエースです。

  2. 2 枚のカードを上から下に 1 つずつ移動します。次のカードが表向きにテーブルに配られます。スペードのツーです。

  3. 3 枚のカードが 1 つずつ移動されます…</p>

  4. これは、n 番目と最後のカードがスペードの n になるまで続きます。

この印象的なトリックは、マジシャンが事前にカードの配置方法を知っている場合 (および偽のシャッフルの方法を知っている場合) に機能します。プログラムは、1 ≤ n ≤ 20000 の指定された数のカードのカードの最初の順序を決定する必要があります。

入力

入力の最初の行は、1 つの正の整数であり、従うべきテスト ケースの数を示します。各ケースは、整数 n を含む 1 行で構成されます。出力

テスト ケースごとに、値 1 から n の正しい順列をスペースで区切って行を出力します。パックの一番上のカードを示す最初の数字など…例

入力: 2

4

5

出力：

2 1 4 3

3 1 4 5 2

今私が考えることができる唯一の解決策は、キューを使用してプロセスをシミュレートすることです。しかし、それはO（n ^ 2）になります。コメントを読んだところ、BITのセグメントツリーを使用することが提案されました。セグメント ツリーと BIT の両方を知っていますが、この質問でそれらを実装する方法を理解できません。これを行う方法を提案してください。ありがとう

4

2 に答える 2

3

この問題を BIT やセグメント ツリーにリンクする必要がある理由がわかりませんが、単純な "O(N^2)" シミュレーションを使用して問題を解決しました。

まず、この問題の制限時間は11sとN == 20000です。これは、O(kN)ソリューションが問題をパスする可能性があることを示しています。単純なシミュレーションではこれが必要ですが、どうにかして最適化できるため、これkは であるべきだと思います。N

N == 5 の場合にシーケンスを構築する方法を見てみましょう。

Round 1, count 1 space starting from first space after last position:        _ 1 _ _ _
Round 2, count 2 spaces starting from first space after last position:       _ 1 _ _ 2
Round 3, count 3 spaces starting from first space after last position:       3 1 _ _ 2
Round 4, count 4 spaces starting from first space after last position:       3 1 4 _ 2
Round 5, count 5 spaces starting from first space after last position:       3 1 4 5 2

素敵なパターンを見ることができます: roundの場合、最後の位置の後の最初のスペースから開始してスペースiを数え、必要に応じてワープする必要があります。i

ただし、重要なステップは次のとおりです。いくつかのラウンドの後、残ったスペースはカウントするスペースよりも小さくなります。modこの場合、時間を節約するために取ることができます!

たとえば、前の例のラウンド 4 では、残りのスペースは 2 つしかありませんが、カウントするスペースは 4 つです。4つ数えたら時間の無駄です。4 ステップをカウントすることは、最後の位置の後の最初のスペースから 4%2 == 0 スペースをカウントすることと同じです。この点は自分で確認できます:)

したがって、コードを使用してこのプロセスをシミュレートできます。

memset(ans, 255, sizeof(ans));
while (cur <= n)
{
    int i, cnt;
    int left = n - cur + 1; // count how many spaces left
    left = cur % left + 1; // this line is critical, mod to save time!

    for (i = pos, cnt = 0; ; ++i) // simulate the process
    {
        if (i > n) i = 1;
        if (ans[i] == -1) ++cnt;
        if (cnt == left) break;
    }

    ans[i] = cur;
    pos = i;

    ++cur;
}
于 2014-09-02T19:13:17.077 に答える
2

この問題を解決するためにフェンウィック ツリー (BIT) を使用する場合は、nevet が投稿した解決策、特にこの部分を詳しく見てください (nevet の描画に感謝します)。

Round 1, count 1 space  starting from first space after last position:       _ 1 _ _ _
Round 2, count 2 spaces starting from first space after last position:       _ 1 _ _ 2
Round 3, count 3 spaces starting from first space after last position:       3 1 _ _ 2
Round 4, count 4 spaces starting from first space after last position:       3 1 4 _ 2
Round 5, count 5 spaces starting from first space after last position:       3 1 4 5 2

上記のアプローチを使用して正しい空きスペースを見つけるには、すべてのスペースを通過する必要があるため、時間の複雑さが O(N) になります (合計の複雑さ O(N^2))。次を使用して次の位置を計算できることに注意してください。

free(next_pos) = (free(current_pos) + next_number) mod free(total) + 1

ここで、free(x) は、位置まで (含む) の空きスペースがいくつあるかを示します。これは next_pos の直接的な式ではありませんが、何を満たす必要があるかを示しているため、この情報を使用して二分探索を行うことができます。

残された唯一のことは、空き領域の計算を行うことです。ここで BIT の出番です。クエリと更新の両方で O(log N) の時間計算量が得られるからです。空き領域を見つける時間の計算量は O(log^2 N) になり、総時間の計算量は O(N log^2 N) になります。

走行速度に関しては：

  • nevetsが提案したアプローチの3.16秒
  • キューを使用して要素をローテーションする 1.18 秒
  • リンクされたリストを使用して回転する0.60秒
  • BIT を使用して 0.02 秒。

速度の向上にはかなり驚いたと言わざるを得ません:-)

PS BIT の使用方法がわからない場合は、すべての値を +1 で更新して初期化してください。スロットを使用済みとしてマークするときは、-1 だけ更新します。それだけです。

于 2015-04-29T19:35:27.277 に答える