1

コンテスト中に改善を試みるためにランダムな TopCoder の問題を調べています。

問題文 

テディはバラが大好きで、トレーシーはユリが大好きです。彼らはこれらの花を広い庭に植えたいと思っています。

vector<int>しかし、町で唯一の花屋は、これらの花をバラとユリで表されたパケットで販売しています. i 番目のパケットには、roses[i] のバラと lilies[i] のユリが含まれています。各パケットは1回のみ購入できます。

Teddy と Tracy は、いくつかの花を購入し、それらを長方形のグリッドに配置したいと考えています。このグリッドは、各セルが正確に 1 つの花を含み、エッジを共有する 2 つのセルが異なる種類の花を含むように配置する必要があります。さらに、テディとトレーシーは、購入したすべての花を使用する必要があります。

Teddy と Tracy は正方形のグリッドが大好きなので、花をできるだけ正方形のグリッドに配置できるように、パケットのセットを購入したいと考えています。より正確には、花を R x C グリッドに配置したいと考えています。ここで、R と C は正の整数で、|RC| となります。(|RC| は RC の絶対値) を最小化します。この最小絶対値を返すか、有効な配置が存在しない場合は -1 を返します。

意味   

クラス： BuyingFlowers

方法： buy

パラメーター： vector <int>, vector <int>

戻り値： int

メソッドの署名: int buy(vector <int> roses, vector <int> lilies)

例

{2, 4}
{4, 2}

戻り値: 1

6 つのバラと 6 つのユリを得るためにすべてのパケットを購入すると、次の配置で 3 x 4 グリッドを作成できます。

RLRL
LRLR
RLRL

この配置の高さと幅の差は 1 です。

これまでの私の考え

そのため、これまでにこの問題についていくつかの考えを持っていたので、それを解決するために重要であると考えています。それらは無視してかまいません。

  • 花によって作成されたすべての長方形には、周囲に偶数のバラとユリがあります。したがって、花で作成できる最大の長方形は、2 つのうち小さい方の数量を取ることで見つけることができます。たとえば、6 つのバラと 4 つのユリがある場合、ユリは 4 つしかないため、作成できる最大サイズの長方形には 4 つが含まれます。バラと 4 つのユリ。

  • 課題は、長方形の各セルを花で埋めなければならないことを考慮すると明らかに発生するため、花の数を考慮して、両方を満たす「最適な」長方形を見つける必要があります。残りの花が存在するための「セル」、および可能な限り正方形に近い.

投稿されたソリューションのいくつかを見てきましたが、コードは非常に難読化され、最適化されている傾向があり (すばやく書くという点で)、作成者がソリューションに対して念頭に置いていた概念を抽出するのが難しい傾向があります。

このような問題をすばやく解決する方法について学びたいと思います。

4

3 に答える 3

0

TopCoder に関して言えば、問題ステートメントの最も重要なセクションの 1 つは制約セクションです。これは通常、制限時間内に何が可能で何が不可能かを決定するためです。

あなたの場合、最大で 16 個のパケットがあります。可能なサブセットの総数 =2^16=65536 は非常に少ないため、パケットのすべてのサブセットを調べて、どれが最適な組み合わせになるかを判断できます。

これを行うには、ビット操作を使用します (C++ の場合)。

for(int i=0;i<(1<<16);i++)
{
 //i represents a subset
 for(int j=0;j<16;j++)
   if(i & (1<<j))
   {
    //j-th packet is present in subset
   }
}

パケットの組み合わせが与えられたら、どのくらいの大きさの長方形を作ることができるか分かりますか?

はい。

ヒント：左上隅にユリを固定した場合、残りの花をどのように配置できますか?
PS : 方法は 1 つだけです。
同様に、左上隅にバラを固定する場合、長方形を埋める方法は 1 つしかありません。

これを見つけたら、サブセットのすべての組み合わせを反復して、どれが最小の |RC| を生成するかを確認します。

さらに質問がある場合はお尋ねください。

于 2013-08-30T03:24:28.753 に答える
0

http://community.topcoder.com/stat?c=problem_statement&pm=11191の例を見ると、2 つの可能性しかないように見えます。

|number of roses - number of lillies| == 1, for odd R and odd C

or

number of roses == number of lillies, for even R or even C

それが本当なら、最も近い 2 つの整数因数 (理想的には平方根) に割り切れる数lillies + roses(ここでnum lillies == num rosesまたは)を見つける方法を探します。|num roses - num lillies| == 1

TopCoder の例には、次のものがあります。

Example 0:     6 + 6 = 12, closest two factors 3x4
Example 1:     5 + 4 = 9, closest two factors 3x3

JavaScript の例:

function closestFactors(n)
{
    var start = Math.floor(Math.sqrt(n))
    while (n % start != 0)
        start--
    return [start,n / start]
}

var roses = [1, 208, 19, 0, 3, 234, 1, 106, 99, 17],
    lillies = [58, 30, 3, 5, 0, 997, 9, 615, 77, 5]

function f(index, currentR, currentL, best)
{ 
    if (roses.length == index)
        return best
    for (var i = index; i < roses.length; i++) 
    {
        var cr = currentR + roses[i],
            cl = currentL + lillies[i]
        if (cr == cl || Math.abs(cr - cl) == 1)
        {
            var cf = closestFactors(cr + cl),
                current = Math.abs(cf[0] - cf[1])
            if (current == 0)
                return 0
            best = best < 0 ? current : Math.min(best,current)
        }
        best = best < 0 ? f(i + 1, cr, cl, best)
                        : Math.min(best,f(i + 1, cr, cl, best))
        if (best == 0)
            return 0
    }
    return best
}

コンソール出力:

f(0,0,0,-1)
36
于 2013-08-30T03:18:49.903 に答える
0

次の質問について考えてみてください:行列 N * M に、行列の半分以上のユリ/バラを配置できますか?

この質問に答えると、問題を終わらせることができます。

于 2013-08-30T01:22:16.617 に答える