8

ここに質問があります（リンク：http：//opc.iarcs.org.in/index.php/problems/FINDPERM）：

数1、...、Nの順列は、これらの数の再配置です。たとえば、
2 4 5 1 7 6 3 8
は1,2、...、8の順列です。もちろん、
1 2 3 4 5 6 7 8
も1、2、...、8の順列です。
Nの各順列に関連付けられているのは、反転シーケンスと呼ばれる長さNの正の整数の特別なシーケンスです。このシーケンスのi番目の要素は、厳密にiより小さく、この順列でiの右側に表示される数jの数です。順列245
1 7 6 3 8
の場合、反転シーケンスは
0 1 0 2 2 120です。
2番目の要素は1です。これは、1が厳密に2未満であり、この順列では2の右側に表示されるためです。同様に、1と3は厳密に5未満であるため、5番目の要素は2ですが、この順列では5の右側に表示されます。
別の例として、順列
8 7 6 5 4 321の反転シーケンス
は012
3 4 5 6 7
です。この問題では、いくつかの順列の反転シーケンスが与えられます。あなたの仕事は、このシーケンスから順列を再構築することです。

私はこのコードを思いついた：

#include <iostream>

using namespace std;

void insert(int key, int *array, int value , int size){
    int i = 0;
    for(i = 0; i < key; i++){
        int j = size - i;
        array[ j ] = array[ j - 1 ];
    }
    array[ size - i ] = value;
}

int main(){

    int n;
    cin >> n;
    int array[ n ];
    int key;

    for( int i = 0; i < n; i++ ){
        cin >> key;
        insert( key, array, i + 1, i);
    }

    for(int i = 0;i < n;i ++){
        cout << array[i] << " ";
    }

return 0;
}

それは正常に機能しており、テストケースの70％に対して正解を示していますが、残りの時間制限を超えています。この質問を解決するための他のより高速なアルゴリズムはありますか？

4

4 に答える 4

7

アルゴには複雑なO(N^2)操作があるため、サイズの配列の場合10^5、実行に時間がかかりすぎます。私はより良い解決策を説明しようとします：

数字がありNます。逆配列を呼び出しましょうI。この問題を解決するには、順列の終わりからまだ自由な位置がどこにあるかを知る必要がありK-thます（この関数を呼び出しましょうF(K)）。まず、数値Nを位置に配置しF(I[N] + 1)、次に数値N-1を位置F(I[N-1] + 1)に配置します。

F次のように計算できます：Mサイズの配列を宣言しますN：1 1 1 ... 1、定義しますS(X) = M[1] + M[2] + ... + M[X]。プレフィックス合計Sとして知られています。プラスマイナスに等しい。数値を位置に配置するたびに、ゼロを。に配置します。時間内に早く見つけるために、バイナリインデックスツリーを使用して時間内にプレフィックスの合計を計算し、バイナリ検索を使用して事前定義された値に等しいものを見つけることを提案できます。F(K)N1XS(X) = KZN + 1 - X(for K = I[Z] + 1)M[X]XO(N)O(logN)XS(X)

そのようなアルゴの全体的な複雑さはですO(N(log(N))^2)。これは Rubyでの実装です（ideoneで正しく操作できます：入力の変更、実行、出力の確認）：

# O(n(log(n))^2) solution for http://opc.iarcs.org.in/index.php/problems/FINDPERM

# Binary Indexed Tree (by Peter Fenwick)
# http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
class FenwickTree

  # Initialize array 1..n with 0s
  def initialize(n)
    @n = n
    @m = [0] * (n + 1)
  end

  # Add value v to cell i
  def add(i, v)
    while i <= @n
      @m[i] += v
      i += i & -i
    end
  end

  # Get sum on 1..i
  def sum(i)
    s = 0
    while i > 0
      s += @m[i]
      i -= i & -i
    end
    s
  end

  # Array size
  def n
    return @n
  end

end

# Classical binary search
# http://en.wikipedia.org/wiki/Binary_search_algorithm
class BinarySearch

  # Find lower index i such that ft.sum(i) == s
  def self.lower_bound(ft, s)
    l, r = 1, ft.n
    while l < r
      c = (l + r) / 2
      if ft.sum(c) < s
        l = c + 1
      else
        r = c
      end
    end
    l
  end

end

# Read input data
n = gets.to_i
q = gets.split.map &:to_i

# Initialize Fenwick tree
ft = FenwickTree.new(n)
1.upto(n) do |i|
  ft.add i, 1
end

# Find the answer
ans = [0] * n
(n - 1).downto(0) do |i|
  k = BinarySearch.lower_bound(ft, q[i] + 1)
  ans[n - k] = i + 1
  ft.add k, -1
end
puts ans.join(' ')

時間のある解決策O(N(log(N)))もあります。ある種の二分探索木を使用します。頂点に番号を付けてBSTを作成し、値ごとに番号1, 2, 3, ... Nを見つけて、時間内に頂点を削除することもできます。K-thO(log(N))O(log(N))

std :: setを使用した解決策も存在する可能性がありますが、現時点では考えられません。

PS。また、Skienna（プログラミングチャレンジ）やCormen（アルゴリズム入門）などのアルゴやオリンピックに関する本を読むことをお勧めします。

PPS。前に説明した間違った解決策をお詫びします

于 2012-10-27T09:07:10.947 に答える
3

最もコストのかかる部分は、明らかに結果配列内の最大100000要素のシフトです。

その配列をより多くのチャンクに分割すると、いくつかの重要な要素によってそれを高速化できます。

10個のチャンクがあり、各チャンクの要素数を覚えている場合は、キーに従って書き込む正しいチャンクを選択し、そのチャンクの要素のみをシフトする必要があります（最大10分の1）。

新しい問題は、チャンク全体で数値を適切に分散させる方法です。

また、リンクリストを使用することもできます：http ：//www.cplusplus.com/reference/stl/list/

挿入には非常に効率的ですが、ランダムなシークには不向きです。ただし、それでもシークは読み取り操作であるため、x要素のシークは配列内のx要素のシフトよりも高速（IDK）になる可能性があります。

次に、組み合わせたアプローチを使用して、複数のポインターを持つリンクリストを作成できるため、常に最も近いポインターから検索できます。

于 2012-10-27T09:00:21.340 に答える
2

これは、C++で必要なコーディングとともに非常に優れたアルゴリズムです。

この問題は、場所7に2がある場合、7を配置する前に2つの空のボックスが残っているという事実を使用して解決されます。したがって、0が8にあり、2が7の場合、逆の結果配列は次のようになります。 7 _ _ _ _。

これで、平方根分解が実行され、挿入が実行されます。

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int n, k = 0, d, r, s, sum, temp, m, diff, check = 1;
    cin >> n;

    d = sqrt(n) + 1;
    int arr[n], result[n], indices[d], arr2[d][d], num = 1;

    for (int i = 0; i < n; i++)
        cin >> arr[i];               //The inversion sequence is accepted.

    for (int i = 0; i < d; i++)
        indices[i] = 0;              //Indices tell where to start counting from in each row.

    for (r = 0; r < d; r++)
    {
        for (s = 0; s < d; s++)
        {
            arr2[r][s] = num;       //Array is filled with 1 to n (after sqrt decomposition).
            num = num + 1;
            if (num == n+1)
            {
                check = 0; break;
            }
        }
        if (check == 0)
            break;
    }

    int l = s;
    while (l >= 0)                  //Non-Zero numbers are shifted to right and 0 placed in
    {                               //empty spaces.
        arr2[r][d-1 - k] = arr2[r][l];
        k = k + 1; l = l - 1;
    }

    k = d-1 - k + 1;
    for (int t = 0; t < k; t++)
        arr2[r][t] = 0;

    indices[r] = indices[r] + k;    //Index of the last row is shifted to first non-zero no.

    for (int i = n-1; i >= 0; i--)
    {
        sum = 0; m = 0;
        while (sum < arr[i] + 1)
        {
            sum = sum + (d - indices[m]); //Empty boxes in each row are counted.
            m = m + 1;
        }

        m = m - 1;
        sum = sum - (d - indices[m]);     //When sum = 1 + corresponding value in inversion
        diff = arr[i] + 1 - sum;          //sequence, then that particular value is made 0
        temp = indices[m] + diff - 1;     //and (that value - 1) is the index of the number
                                      //to be placed in result array.
        result[arr2[m][temp] - 1] = i+1;
        for (int w = temp - 1; w >= indices[m]; w--)
        {
            arr2[m][w + 1] = arr2[m][w];  //Then, 0 is shifted to just before non-zero number
        }                                 //in the row, and the elements are shifted right
        arr2[m][indices[m]] = 0;          //to complete the sort.
        indices[m] = indices[m] + 1;
    }                                     //This is done n times for 1 to n integers thus
                                      //giving the permutation in reverse order in result
    for (int p = n-1; p >= 0; p--)        //array.
        cout << result[p] << ' ';

    return 0;
}
于 2012-11-25T11:52:42.097 に答える
1

複雑さがO（n ^ 2）であるため、アルゴリズムはこの問題に対して効率的ではありません。これは、一部の入力ケースで10^10の操作を意味します。あなたはより安い解決策を考え出さなければなりません。

次のアルゴリズムをお勧めします（1からNまでのインデックス）：

for i=1 to N
   input a(i)
   if i==1 insert 1 into b
   else insert i into b at place i-a(i)
end
于 2012-10-27T09:13:20.593 に答える