6

Google Code Jam では、大きな入力の問題を解くことができれば、小さな入力の解決で 2 倍または 3 倍のポイントが得られます。

しかし、私はこれのポイントを理解していません。任意の正の数のケースを処理できるプログラムを作成すると、10 の入力ケースと 10000 の入力ケースを処理できます。

したがって、小さな入力の問題を解決すると、コードを変更することなく、大きな入力についても解決できるはずです。

何か不足していますか？

4

4 に答える 4

7

何か不足していますか？

はい - 制限時間に間に合いません。O(n^2)多くの場合、小さな入力 (アルゴリズムやアルゴリズムなど)に対してはうまく機能するアルゴリズムがO(2^N)、大きな入力に対しては時間がかかりすぎて、大幅に異なるアプローチが必要になります。

たとえばO(N^2)、最長の昇順サブシーケンスを見つけるアプローチは、1 つの配列を使用して 4 行のコードでコーディングでき、数百項目の入力に対してはうまく機能します。ただし、そのアプローチは何十万ものアイテムに対しては失敗し、ツリーまたはバイナリ検索を使用する高度なアプローチが必要になります。その別のアプローチはコーディングに時間がかかるため、より多くのポイントで報いるのが自然です。

于 2013-04-14T09:51:51.090 に答える
1

Google Code Jam の小さい入力と大きい入力の違いは、主にケースの数ではありません。実際には、大きな入力は小さな入力よりもケースが少ない場合があります。しかし、大きな入力の場合はより困難です。(これは多くの場合、より大きなことを意味し、名前の由来です) 入力の数が 2 倍の場合、解を見つけるのに 2 倍の時間が必要になる場合がありますが、これは問題にならない可能性があります。しかし、入力が 2 倍難しい場合は、2 倍以上の時間が必要になる可能性があります。

于 2013-04-14T12:40:53.450 に答える
1

これらの 2 つの入力は、次のフィールドで異なる場合があります。

  1. 問題入力の制限 たとえば、複雑なアルゴリズムを使用して問題の小さな入力を解決できるかもしれませんが、O(n^2)複雑なより優れたアルゴリズムを使用して大きな入力を解決する必要がありますO(log n)。

  2. テストケースの数 これは、アルゴリズムを選択する際にも重要になる可能性があります。

  3. テストケース の難しさ 通常、入力が大きいほど、境界条件などのテストケースが難しくなります。

于 2013-04-14T09:55:42.313 に答える
1

あなたはそこで間違っています。プログラミング言語は、特定のデータ型を使用してデータを格納します。多くの場合、データ型は大きなデータ値を保持できません。したがって、これらの大きなデータ値を組み込むようにコードを変更する必要があります。

たとえば、C を使用してフィボナッチ数を出力する場合、次のような単純なコードになります。

long int first,second,third;
first=1;
second=1;
ct=0;
while(ct < Limit)
{
   third=first + second;
   first = second;
   second = third;
   printf("\n%d",third);
   ct++;
}

このコードは正しいですが、C では が 4 バイト (32 ビット) であるため、フィボナッチ数 > 2 32 (Limitが非常に大きい場合に発生) の場合は正しくない結果が得られます。intlong int

したがって、C のデータ型が不足しているため、正しいアルゴリズムは失敗します。解決するには、独自のデータ構造を実装する必要があります。

于 2013-04-14T09:55:46.977 に答える