私はこの問題を練習していましたが、すぐに正しいアルゴリズムを見つけましたが、実装するには奇妙なものがありました。最初は、整数型のオーバーフローに噛まれたことに気付きました。そのため、__int64を使い始めました。それは私が次の奇妙なことに気づくときです。だから最初に、ここに私のコードは...CodeJam最小スカラー製品の問題
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
const string cInputFileName = "E:\\CodeJamInputs\\d-large-practice.in";
const string cOutputFileName = "E:\\CodeJamInputs\\d-large-practice.out.txt";
__int64 FindSmallestProductOfSums(const vector<int> &iVec1, const vector<int> &iVec2)
{
vector<int> v1 = iVec1;
vector<int> v2 = iVec2;
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end(), greater<int>());
__int64 productOfSumsA = inner_product(v1.begin(), v1.end(), v2.begin(), 0);
__int64 productOfSumsB = 0;
for(vector<int>::size_type i = 0; i < v1.size(); ++i)
productOfSumsB += (__int64)v1[i] * (__int64)v2[i];
return productOfSumsB;
}
int _tmain(int argc, _TCHAR* argv[])
{
ifstream inputFile(cInputFileName, ifstream::in);
ofstream outputFile(cOutputFileName, ofstream::out);
if(inputFile.is_open() && outputFile.is_open())
{
int numCases;
inputFile >> numCases;
for(int i = 0; i < numCases; ++i)
{
int vectorSizes;
inputFile >> vectorSizes;
vector<int> vec1, vec2;
for(int j = 0; j < vectorSizes; ++j)
{
int value;
inputFile >> value;
vec1.push_back(value);
}
for(int j = 0; j < vectorSizes; ++j)
{
int value;
inputFile >> value;
vec2.push_back(value);
}
__int64 smallestProductOfSums = FindSmallestProductOfSums(vec1, vec2);
outputFile << "Case #" << (i + 1) << ": " << smallestProductOfSums;
outputFile << endl;
}
}
inputFile.close();
outputFile.close();
}
私は、2つのベクトルについて2つの計算をしています。 1つはSTL inner_productを使用し、もう1つは手作業で繰り返します。 goofyとは、問題の大きなデータセットに対してinner_productメソッドが間違ったリターンをもたらし、手作業が正しいことです。 STLコードを踏んで、Ty Val変数がintであるように見えたように、オーバーフローが発生したように見えましたが、確かに結果が蓄積されています。
私は、inner_productを使用してこの質問を解決した人がいると思いますが、違いは何だと思いますか？私はinitパラメタとしてgigglesの0LLを渡そうとしましたが、実際には別の答えが返されましたが、それでも正しいものはありません。奇妙なことに、明示的な__int64キャストを追加する前に、手のメソッドと同じ答えが返されました。だから間違いなくタイプとオーバーフローでここで何か奇妙なことが起こっています。それにも関わらず、私は小規模と大規模の両方のセットに対して正しい答えを得ましたが、私はそれを働かせることができなかったinner_productを使用している人がいることを知りました。私の手のひらソリューションは小規模と大規模の両方で動作しますが、小さなデータセットではinner_productが機能しましたが、大きなデータセットでは機能しませんでした。
以下は、問題の各ケースの出力です（大きなデータセットの合計は10個です）。いずれの場合も、3つの出力があります。 1番目は手計算メソッド（正解）で、2番目はinner_productにinit（0）（誤答）を使用し、3番目はinner_productをinit（0LL）で使用しています。加えて、ちょうどちょっとして、私はx64ターゲットとしてもコンパイルしましたが、結果は同じでした。
ケース＃1：-7839202227936 ケース＃1：-886912736 ケース＃1：-1104693507808
ケース＃2：7999201712083 ケース＃2：1972606931 ケース＃2：1127254038483
ケース＃3：-1313429236847 ケース＃3：830755729 ケース＃3：-175262903407
ケース＃4：-3710387739618 ケース＃4：464004126 ケース＃4：-897 30309090
ケース＃5：-3414920765916 ケース＃5：-421765596 ケース＃5：-82026144220
ケース＃6：-1271937742993 ケース＃6：-627423377 ケース＃6：-30692194449
ケース＃7：-1964394407029 ケース＃7：-1594352757 ケース＃7：-40249058421
ケース＃8：-1884282427866 ケース＃8：1208215078 ケース＃8：-101871000026
ケース＃9：-4044533757860 ケース＃9：1325434972 ケース＃9：-106048747428
ケース＃10：-838783451371 ケース＃10：-1264828651 ケース＃10： -44214501611
長いポストに申し訳ありませんが、私は興味深い問題だと思いました。次のように