Box Factoryは、Google Code Jam 2012 Round 1C の問題です。これは、Longest Common Subsequence 問題に似ており、O(n^4) の解が与えられています。ただし、分析の最後に、別の改善によりこれを再び O(n^3) に減らすことができると言われています。ソリューションに対してどのような最適化を行うことができるのか疑問に思っています。
質問する
384 次
1 に答える
3
O(n^4) アルゴリズム
動的計画法のアプローチでは、f[x][y] = ボックスの最初の x 回の実行とおもちゃの最初の y 回の実行を使用して、ボックスに配置できるおもちゃの最大数を解きます。
これは、a+1 と x の間の最後のタイプのボックスと、b+1 と y の間の最後のタイプのおもちゃを考慮することによって解決されます。
O(n^4) アルゴリズムは、a と b のすべての選択肢をループしますが、a と b の重要な値のみを考慮することで単純化できます。
O(n^3) アルゴリズム
重要な点は、a,b があり、おもちゃより箱の数が多い場合、a を変更してさらに箱を増やしても意味がないということです (これは、これ以上の製品を作るのに決して役立たないため)。同様に、箱よりも多くのおもちゃがある場合、b のすべてのケースを考慮することをスキップできます。これにより、さらに多くのおもちゃが得られます。
これは、より多くのおもちゃを持つこととより多くの箱を持つことの間の a,b の境界をたどる内部ループの O(n) アルゴリズムを示唆しています。a=x-1、b=y-1 から始めて、現在のおもちゃや箱の数に応じて a または b を減らすだけなので、これは非常に簡単です。(等しい場合は、両方を減らすことができます。)
アルゴリズムの各ステップでは、a または b のいずれかが 1 ずつ減少するため、この反復では、元の方法の x*y ステップではなく、x+y ステップが必要になります。
x、y のすべての値に対して繰り返す必要があるため、全体的な複雑さは O(n^3) です。
その他の改善
さらなる改善は、各タイプの前回の実行のインデックスを保存することです。これにより、アルゴリズムのいくつかのステップを 1 つの動きに折りたたむことができるようになります (これは、実行に戻って初めてスコアが改善されることがわかっているためです)。正しいタイプ)。ただし、これは最悪の場合でも O(n^3) になります (同じ種類のすべてのボックス/おもちゃ)。
もう 1 つの実用的な改善方法は、タイプが連続した位置で同じであった実行を結合することです。これにより、以前の改善で最悪のケースの動作を明らかにするように設計されたテスト ケースが大幅に簡素化される可能性があります。
于 2012-07-22T12:08:27.263 に答える