0

しばらくの間、問題 201を解決しようとしてきましたが、そのような大規模なセットの解決策を思いつくことができませんでした。到達可能な合計が最大 300,000 を超えないことを考えると、ランダム化されたアルゴリズムを試しましたが、計算時間が膨大な小さなセットでしか機能しませんでした。次に、動的プログラミングのアプローチを試みましたが、成功しませんでした。

私はすでにあきらめましたが、この問題を効率的に解決する方法に興味があります。

4

1 に答える 1

1

ネタバレ注意！

この問題にどのようにアプローチしたかについていくつかのヒントを与えることを考えました（そして、そのような問題にアプローチする一般的な方法でどのように適合するかを示しました）

ヒント 1: 次の関数の再帰を定式化 (または単にコードを記述) します

boolean existsRepresentation(int number, int maximalIntegerToSquare, int numberOfSquares)

ここで、引数 number が x^2 形式の numberOfSquares 二次項の合計として表現される場合、関数は true を返します。ここで、最大 x は maximalIntegerToSquare です。したがって

5=2^2+1^2 であるため、existsRepresentation(5,2,2) は true を返しますが、existsRepresentation(5,2,3) は、5=x^ となる異なる x,y,z<=2 がないため、false を返します。 2+y^2+z^2

ヒント 2: 関数の再帰を定式化 (またはコードを記述) する

boolean existsUniqueRepresentation(int number, int maximalIntegerToSquare, int numberOfSquares)

ここで、引数 number が x^2 の形式の numberOfSquares 二次項の合計として UNIQUE 表現を持つ場合、関数は true を返します。ここで、最大 x は maximalIntegerToSquare 以下です (再帰には関数 existsUniqueRepresentation と関数 existsRepresentation の両方が含まれる必要があります)。引数の値を小さくしてヒント 1 から)。したがって

existsUniqueRepresentation(5,2,2) は、5=2^2+1^2 であり、2 つの異なる平方 x^2+y^2 x<y (最大 y =2 必要に応じて、またはそれ以外の場合)

existsUniqueRepresentation(5,2,3) は false です。単純に、2 以下の 3 つの異なる数の 3 つの平方の合計として 5 の表現がない (したがって一意の表現がない) (x、y、z がない) ためです。 1<=x<y<z<=2 ..)

89=8^2+4^2+3^2 および 89=7^2+6^2+2^2 であるため、existsUniqueRepresentation(89,8,3) および existsUniqueRepresentation(89,9,3) は false です。

あなたが自分自身に与えたヒント3：existsRepresentation（）またはexistsUniqueRepresentation（）のいずれかによって返されるすべての値をキャッシュする必要があるという意味で、動的プログラミングを使用してください（実際、これは教科書では「メモ化」と呼ばれ、動的プログラミングは方法を指します再帰呼び出しを行わずに計算するためにキャッシュされた値を整理しますが、ポイントは常にサブ問題の解決策をキャッシュすることです)。

したがって、一般的なアプローチは次のとおりです。問題を再帰として定式化し、移動するすべてをキャッシュします。（PCに十分なメモリがあるすべてのもの、つまり..）

それは機能します（ここおよび他の多くの問題で）！

于 2013-03-21T09:39:34.573 に答える