2

要素が最大10 ^ 9になる非常に大きな整数の配列が与えられた場合、最大のAND値を持つペアを見つけるにはどうすればよいですか。私の現在のアプローチは、可能なすべてのペアを計算し、それをトラバースして最大値を見つけることですが、非常に遅いです。他のアプローチはありますか？

4

2 に答える 2

0

連続する 2 つの数 n - 1 と n のビット パターンが異なる最初の位置を見てください。少し考えてみると、このビットは n の場合は 1、n - 1 の場合は 0 でなければならないことがわかります。それ以外の場合はありえません。そのビットの左側ではすべてが等しく、そのビットの右側では 2 つのうち大きい方が 0 のみ、小さい方が 1 のみです。それ以外のことはできません。

したがって、次のようになります。

n           -> (common prefix) 1 0*
n - 1       -> (common prefix) 0 1*
-----------------------------------
n & (n - 1) -> (common prefix) 0 0*

例：

88          -> 101 1 000
87          -> 101 0 111
------------------------
88 & 87     -> 101 0 000

共有プレフィックスは空にすることができ、繰り返しビット (0* と 1* のもの) を持つスター付きテールは空にすることができます。

末尾は常にすべてゼロになるため、(n - 1) & (n - 2) は n & (n - 1) よりも大きくなければなりません。 n - 2) 最後のビットのみが欠落しています。また、n までの範囲内の他のすべてのペア AND よりも大きくなければなりません。

末尾が存在しない場合 (つまり、n が奇数の場合)、n & (n - 1) は、n に先行する範囲全体に対して最大の AND 値を持ちます。明らかでない場合: 「テールが存在する」の別の表現は「n は偶数」です。

特別な処理が必要なケースの 1 つは、B = A + 1 の場合です。つまり、範囲の長さが可能な限り短い場合です。その場合、B が偶数の場合にフォールバックする (B - 2) はありません。

したがって、A < B の範囲 [A, B] の最大 AND の計算は次のようになります。

if ((B & 1) == 1 || A > B - 2)
    return B & (B - 1);
else
    return (B - 1) & (B - 2);

完全な Monty については、HackerEarthでの私の投稿をご覧ください。

回答を投稿して初めて、このトピックで議論されている問題が、HackerEarth での最大 ANDとは少し異なることがわかりました。これは、処理が連続した範囲の数値ではなく、入力の特定のベクトルに対して行われるためです。

上記のスキームは、ソートされたシーケンスの下方スキャン中に適切な連続値が発見された場合でも、アーリーアウト条件を提供できますが、それが役立つ可能性はごくわずかです。

これは、最後から逆方向にスキャンすることにより、ソートされたシーケンスで最高の共有ビットを特定できる関数です。通常、完了する前にスキャンする必要がある要素はごくわずかです。ビットを共有せずに、最大で B ビットの B + 1 を超える値を選択することは不可能であるため、関数は、ソートされたシーケンスの上端で対数的に少数の値のみを調べることによって、共有される上位ビットを見つけなければなりません。

static int common_high_bit (int[] v, int lo, int hi)
{
    int shared = 0;

    for (int seen = 0, i = hi - 1; i >= lo && v[i] >= shared; --i)
    {
        int m = shared | seen & v[i];

        if (m > shared)  // discovered a higher shared bit
        {
            m |= m >>  1;
            m |= m >>  2;
            m |= m >>  4;
            m |= m >>  8;
            m |= m >> 16;

            shared = m;
        }

        seen |= v[i];
    }

    return shared - (shared >> 1);
}

ただし、シーケンス全体をソートする必要はありません。ヒープソートの「ヒープ化」ステップ (O(n) で実行可能) を実行し、最大の値を 1 つずつ抽出して、ベイルアウトするか入力が使い果たされるまで上記のアルゴリズムにフィードするだけで十分です。

最上位ビットが識別されたら、このビット セットを持つすべての値をシーケンスから抽出し、ビット k とその左側のすべてをゼロにし、結果を同じプロセスにかける必要があります。候補セットが扱いやすいサイズに縮小されると、単純な 2 次アルゴリズムは、大きな機械よりも効率的に残りを処理できます。

注：IVladの回答が示唆するように、共有上位ビットは必ずしもMSBではありません。例：

101xxxxx
 11xxxxx

ご覧のように、最上位の共有ビットはどちらの数値の MSB でもありません。

同様の理由で、共有上位ビットとその残りをマスクした後の残りの候補セットの値の順序について、多くを想定することはできません。

しかし、異常で不都合なコンスタレーションが多数存在することはあり得ないため、状況は暗いものではありません。また、共有された上位ビットがそこの値の MSB になるまでシーケンスを下回ったら、対数的にさらにいくつかの値を抽出する必要があるだけです。次のステップの候補セットを完成させます。

于 2016-07-13T17:36:34.870 に答える