C++ベクタとメモ化ランタイムエラーの問題

Question

Codechefでhereという問題が発生しました。私はメモを作成するためにベクトルを使用しようとしています。私はまだプログラミングでは新しく、STLコンテナにはあまり慣れていないので、ルックアップテーブルにvectorを使用しました。 （しかし、私はmapを使って問題を解決することを提案しました）。

私の質問は、以下に示すソリューションが実行時エラーになる方法です。エラーを得るために、問題の境界値（100000000）を入力として使用しました。 Netbeans IDEで表示されるエラーメッセージはRUN FAILED (exit value 1, total time: 4s)で、入力は1000000000です。ここでは、コードは次のようになります。

#include <iostream> 
#include <cstdlib> 
#include <vector> 
#include <string> 

#define LCM 12 
#define MAXSIZE 100000000 
using namespace std; 
/* 
* 
*/ 
vector<unsigned long> lookup(MAXSIZE,0); 

int solve(int n) 
{ 
    if (n < 12) { 
     return n; 
    } 
    else { 
     if (n < MAXSIZE) { 
      if (lookup[n] != 0) { 
       return lookup[n]; 
      } 
     } 

      int temp = solve(n/2)+solve(n/3)+solve(n/4); 
      if (temp >= lookup[n]) { 
       lookup[n] = temp; 
      } 
      return lookup[n]; 

    } 
} 
int main(int argc, char** argv) { 
    int t; 
    cin>>t; 
    int n; 
    n = solve(t); 
    if (t >= n) { 
     cout<<t<<endl; 
    } 
    else { 
     cout<<n<<endl; 
    } 
    return 0; 
} 

Answer 1

は、私は疑う、彼はあなたも[n]は、ルックアップをやっているかの状態では、私が気づい100000000

一つのものを入力しますn == MAXSIZEの場合（この正確な条件で） C++は0でインデックス付けされたベクトルを使用するため、これはベクトルの終わりを超えて1になります。

if (n < MAXSIZE) { 
    ... 
    } 

     ... 
     if (temp >= lookup[n]) { 
      lookup[n] = temp; 
     } 
     return lookup[n]; 

私は、アルゴリズムが何をしているのかを推測することはできませんが、私がダウンして低くする必要があり、あなたは、この境界条件にエラーを返すことができ、「場合」最初の閉じ括弧}を考えます。

Answer 2

あなたは十分なメモリを持っていないか、100,000,000 unsigned long Sを格納するのに十分な連続アドレス空間を持っていないのいずれか。これはメモリの問題であれば、彼はすでにプログラムが実際に実行されることを言ったので

Answer 3

これは主にメモリの問題です。ベクトルの場合、連続したメモリ割り当てが必要です（一定の時間参照の約束に追いつくことができるように）。あなたのケースでは、8バイトの倍数で、基本的にはあなたのマシンに約762 MBのメモリを1つのブロックで与えるように要求しています。

あなたはどの問題を解決しているのか分かりませんが、あなたはBytelandianコインを解決しているようです。このため、マップを使用する方がはるかに優れています：

1. テストケースの実行では、すべての100000000ケースの値を保存することはほとんどありません。だから、あなたが必要とするのは、あなたが実際にメモした値だけのためにメモリを割り当てる方法です。
2. あなたがいても、一定の時間の検索は必要ありません。あなたのプログラムを高速化しますが、std :: mapは木を使って対数的なルックアップ時間を与えます。そしてそれは、連続して762メガバイトを使い切るという要求をなくします。 762メガバイトは大したことではありませんが、単一のブロックで期待しています。

だから、あなたの状況で使用するのが最善のことはstd :: mapです。あなたの場合、実際にstd::vector<unsigned long>をstd::map<int, unsigned long>に置き換えると、mapも同様に動作し、[]オペレータアクセス[ほとんどの場合、それはすべきです]。