10

セット {1, 2, 3, ...,N} が与えられます。特定のセットのサブセットの最大サイズを見つけて、サブセットの任意の 2 つの数値の合計が特定の数値 K で割り切れないようにする必要があります。N と K は最大 2*10^9 になるため、非常に高速なアルゴリズム。複雑さ O(K) のアルゴリズムしか思いつきませんでしたが、これは遅いです。

4

5 に答える 5

5

最初にすべての集合要素 mod k を計算し、単純な問題を解決します。特定の集合のサブセットの最大サイズを見つけて、サブセットの任意の 2 つの数値の合計が特定の数値 K と等しくならないようにします。この集合を除算します。 set(i) と set(ki) を同時に選択できない 2 つのセット (i と ki) にします。

int myset[]
int modclass[k]

for(int i=0; i< size of myset ;i++)
{
    modclass[(myset[i] mod k)] ++;
}

選ぶ

for(int i=0; i< k/2 ;i++)
{ 
    if (modclass[i] > modclass[k-i])
    {
        choose all of the set elements that the element mod k equal i
    }
    else
    {
        choose all of the set elements that the element mod k equal k-i
    }
}

最後に、要素 mod k が 0 または k/2 に等しい要素から 1 つの要素を追加できます。

複雑さ O(K) のアルゴリズムを使用したこのソリューション。

動的配列を使用してこのアイデアを改善できます。

for(int i=0; i< size of myset ;i++)
{
    x= myset[i] mod k;
    set=false;
    for(int j=0; j< size of newset ;j++)
    {
        if(newset[j][1]==x or newset[j][2]==x)
        {
            if (x < k/2)
            {
                newset[j][1]++;
                set=true;
            }
            else
            {
                newset[j][2]++;
                set=true;
            }
        }
    }
    if(set==false)
    {
        if (x < k/2)
        {
            newset.add(1,0);
        }
        else
        {
            newset.add(0,1);
        }
    }
}

複雑さ O(myset.count) のアルゴリズムを選択できるようになりました。セットを読み取るには O(myset.count) が必要なため、アルゴリズムは O(myset.count) を超えています。このソリューションの複雑さは O(myset.count^2) であり、入力に応じてアルゴリズムを選択できます。O(myset.count^2) と o(k) を比較します。より良い解決策として、mod k に基づいて myset をソートできます。

于 2012-12-22T11:55:33.793 に答える
4

数値のセットは、N に対して常に 1 から N であると想定しています。

最初の N-(N mod K) 数を考えてみましょう。0 から K-1 までの mod K の削減を伴う、K 個の連続した数値の form floor(N/K) シーケンス。各グループについて、floor(K/2) は、floor(K/2) の別のサブセットの否定 mod K である縮小 mod K を持つために削除する必要があります。K個の連続した数の各セットからceiling(K/2)を保つことができます。

次に、残りの N mod K 数を考えます。1 から始まる mod K の削減があります。私は正確な制限を計算していませんが、N mod K が約 K/2 未満であれば、それらすべてを維持することができます。そうでない場合は、それらの最初の上限 (K/2) について維持できます。

================================================== ========================

ここでのコンセプトは正しいと思いますが、まだすべての詳細を把握していません。

================================================== ========================

これが問題と答えの私の分析です。|x| に続くもの はフロア(x)です。このソリューションは、@ Constantine の回答のも​​のと似ていますが、いくつかのケースで異なります。

最初の K*|N/K| を考えてみましょう。要素。それらは |N/K| で構成されます。K を法とするリダクションの繰り返し。

一般に、|N/K| を含めることができます。k modulo K である要素は、次の制限に従います。

(k+k)%K がゼロの場合、k modulo K である要素を 1 つだけ含めることができます。これは、k=0 および k=(K/2)%K の場合であり、偶数 K の場合にのみ発生します。

つまり、|N/K| が得られます。* |(K-1)/2| 繰り返しからの要素。

省略された要素を修正する必要があります。N >= K の場合、0 mod K 要素に 1 を追加する必要があります。K が偶数で N>=K/2 の場合、(K/2)%K 要素に 1 を追加する必要もあります。

最後に、M(N)!=0 の場合、繰り返し要素の部分的または完全なコピー、min(N%K,|(K-1)/2|) を追加する必要があります。

最終的な式は次のとおりです。

|N/K| * |(K-1)/2| +
(N>=K ? 1 : 0) +
((N>=K/2 && (K%2)==0) ? 1 : 0) +
min(N%K,|(K-1)/2|)

これは、K を含む場合によっては @Constantine のバージョンとは異なります。たとえば、N=4、K=6 を考えてみましょう。正解は集合 {1, 2, 3} の大きさである 3 です。@コンスタンティンの式は |(6-1)/2| を与えます = |5/2| = 2. 上記の式は、最初の 2 行でそれぞれ 0、3 行目で 1、最後の行で 2 となり、正解になります。

于 2012-12-22T09:59:00.347 に答える
3

式は

|N/K| * |(K-1)/2| + ost 

ost =
if n<k:
  ost =0
else if n%k ==0 :
  ost =1    
else if n%k < |(K-1)/2| :
  ost = n%k
else:
  ost = |(K-1)/2|

ここで |a/b| 例: |9/2| = 4 |7/2| = 3

例 n = 30 、k =7 ;

1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30

1 2 3 |4| 5 6 7. - は最初の行です。8 9 10 |11| 12 13 14 - 2 行目 各行で最初の 3 つの数値を取得すると、このサブセットのサイズを取得できます。また、( 7 14 28) から 1 つの数字を追加することもできます。

最初の 3 つの数値を取得する (1 2 3) は数値 |(k-1)/2| です。. この行の番号は |n/k| です。. 剰余がない場合は、数字を 1 つ追加できます (たとえば、最後の数字)。残基 < |(k-1)/2| の場合 最後の行ですべての数値を取得し、それ以外の場合は |(K-1)/2| を取得します。

例外的なケースをありがとう。k>nの場合、ost = 0

于 2012-12-22T10:26:12.697 に答える