1

Google codeJam の資格ラウンドの問題の 1 つは、与えられた 2 つの整数の間に「リサイクルされたペア」がいくつあるかを見つけることでした。

これが私の解決策でしたが、大きなデータ入力セットには十分な速度ではありませんでした。@a = 10, @b = 200000 のようなものを指定すると、遅くなり始めます。

私の解決策は O(2^n) (大きな O 分析についてはまだしっかりと把握していません) になると思いますが、これは恐ろしいことです。より高速なアルゴリズムを使用して、このような 2 つのループを反復する標準的な方法があるかどうか疑問に思っていましたか?

def getPairs
    (@a..@b).each do |n|
      (n..@b).each do |m|
        if (containsSame(n,m)) && (isMatch(@a, n, m, @b))
          @recycledPairs += 1
        end
      end
    end
  end

編集: Google CodeJam サイトから:

順序を変更せずにnの後ろから前にいくつかの数字を移動することによってmを取得できる場合、明確な正の整数のペア（n、m）がリサイクルされるとしましょう。たとえば、(12345, 34512) は、12345 の末尾から 345 を前に移動することで 34512 を取得できるため、リサイクルされたペアです。n と m は、リサイクルされたペアになるために同じ桁数でなければならないことに注意してください。n も m も先行ゼロを持つことはできません。

4

3 に答える 3

3

正しい解決策については、この問題の公式分析を読むことができます。

基本的に、解決策は、 より大きく、各nより大きくないすべての個別の回転を計算することです。Bn

于 2012-04-15T12:55:36.430 に答える
1

説明には、「リサイクルされたペアになるには、n と m の桁数が同じでなければならないことに注意してください」と書かれています。

あなたの内側のループはそれを考慮していません。@a = 2 および @b = 20,000 の場合、内部ループのチャンク全体を切り取ることができます。が 2 桁の場合n、 の 2 桁の値のみをテストする必要がありますm。内側のループの上限を注意深く見てください。

于 2012-04-15T10:53:30.403 に答える
1

From the statement: max b is at most 2*10^6. As with all codejam problems you have multitests.

Step 1: Precalc. For each number n = [1..maxb], save all cycled from it numbers that are strictly less then it(no more than 7 for each) e.g

10 - 1
321 - 132, 213

Step 2: for each test. Walk through each number from A to B, and count the numbers of "cycled" that are between A and B.

Time complexity: Step 1 works in (number of digits) for each number, i.e. O(ln n). You have to do it b times. All in all O(b*ln b). Same goes for step 2. This works less than a second on big test case.

于 2012-04-15T10:59:35.790 に答える