Count Sort でRuntime Error

[cotora]

c++勉強のため、AOJ (Aizu Online Judge)にあるCount Sortという問題（リンク）に取り組んでいるのですが、n=2000000のテストケースでRuntime Errorとなってしまいます。
一応、問題中にある擬似コードに沿っているつもりなのですが、どこがまずいのかご指摘いただけると嬉しいです。

私が書いているコードです。

コード:

#include <stdio.h>
#include <iostream>
using namespace std;
#define MAX_ELEM 10001

int n;

void sort(int A[], int B[], int C[]){
  for (int i=0; i<n; i++){
    scanf( "%d", &A[i]);
    C[A[i]]++;
  }
 
  for (int i=1; i<MAX_ELEM; i++){
    C[i] = C[i] + C[i-1];
  }
  
  for (int i=n-1; i>=0; i--){
    int idx = C[A[i]]-1;
    B[idx] = A[i];
    C[A[i]]--;
  }
}

int main(){
  scanf( "%d", &n);
  int A[n];
  int B[n];
  int C[MAX_ELEM]; // 0 to 10000
 
  sort(A, B, C);
  
  printf("%d", B[0]);
  for (int i=1; i<n; i++){
    printf("%s%d", " ", B[i]);
  }
  printf("\n"); 
}

[みけCAT]

巨大な自動変数を宣言しているため、スタックオーバーフローの疑いがあります。
main関数内のAおよびBを可変長配列ではなくポインタにし、new[]を用いてメモリを動的確保するようにするとどうなりますか？

[みけCAT]

一応、問題中にある擬似コードに沿っているつもりなのですが

擬似コードではCがきちんと初期化されているのに、cotoraさんのコードでは初期化されていないですね。
初期化をしましょう。

[YuO]

直接関係ありませんが，記述されているコードは C でしょうか。 C++ でしょうか。

• Cだと，using namespace std;は不正。また，通常<iostream>は存在しない。
• C++だと，int A[n];およびint B[n];は不正。

[みけCAT]

オフトピック

C++だと，int A[n];およびint B[n];は不正。

C++標準規格では不正ですが、拡張があるGCCやclangでは使えます。
(個人的には使わないべきであると思いますが)

[みけCAT]

オフトピック

ついでに蛇足を書くと、

Cだと，using namespace std;は不正。

コンパイルオプションによって定義されるマクロによっては、不正とは限りません。
もっとも、AOJではそんな変なマクロは定義されないでしょうが。

[あんどーなつ]

私もやってみました。とりあえず、CountingSort関数以外をあげておきます。

ex1.cpp

コード:

#include <iostream>
#include <cstdint>

using namespace std;

typedef uint16_t INTK;
typedef uint32_t INTN;
typedef uint32_t INTC; // max(c) = 2 * max(n)

void CountingSort(INTK *a, INTK *b, INTC *c,
    INTK k, INTN n)
{
(省略)
}

int main()
{
    INTN n;
    cin >> n;
    INTK *a = new INTK[n+1]; //a[0]は使わない
    for (INTN i = 1; i <= n; ++i) cin >> *(a+i);
    INTK k = 0;
    for (INTN i = 1; i <= n; ++i)
        if (*(a+i) > k) k = *(a+i);
    INTK *b = new INTK[n+1]; //b[0]は使わない
    INTC *c = new INTC[k+1];
    CountingSort(a, b, c, k, n);
    for (INTN i = 1; i <= n; ++i) cout << *(b+i) << " ";

    return 0;
}

大きな問題を生成するperlスクリプト

コード:

$n = 2000000;
$k = 10000;
print($n, "\n");
for ($i = $n - 1; $i >= 0; $i--) {
        print(($i % $k), " ");
}
print("\n");

[あんどーなつ]

すみません、return 0;の前に次の三行が必要です。

コード:

    delete [] a;
    delete [] b;
    delete [] c;

[あんどーなつ]

オフトピック

ちなみに今知ったのですけど、cinとscanfだと実行時間に10倍くらいの違いがあるようですね。

cin.cpp

コード:

#include <iostream>
int main() {
        int n, tmp;
        cin >> n;
        for (int i = 0; i < n; ++i) cin >> tmp;
        return 0;
}

scanf.cpp

コード:

#include <cstdio>
int main() {
        int n, tmp;
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) scanf("%d", &tmp);
        return 0;
}

実行結果 (test2は私がperlスクリプトで作成したテキストファイル)

コード:

$ g++ cin.cpp -std=c++11 -o cin
$ g++ scanf.cpp -std=c++11 -o scanf
$ time ./cin < test2

real    0m3.193s
user    0m3.156s
sys     0m0.015s
$ time ./scanf < test2

real    0m0.426s
user    0m0.390s
sys     0m0.000s

[あんどーなつ]

オフトピック

自前の整数読み取り関数も作ってみました。
getint.cpp

コード:

#include <cstdio>

using namespace std;

inline int getint() {
    unsigned char c;
    do { c = getchar(); }
    while (c == ' ' || c == '\n');
    int res = c - '0';
    while ((c=getchar()) >= '0' && c <= '9') {
        res *= 10;
        res += c - '0';
    }
    return res;
}

getint2.cpp

コード:

#include <cstdio>

using namespace std;

constexpr size_t BUFLEN = 1024;
unsigned char buf[BUFLEN];
size_t cnt = BUFLEN - 1;

inline unsigned char rd() {
    ++cnt;
    if (cnt == BUFLEN) {
        fread(&buf, 1, BUFLEN, stdin);
        cnt = 0;
    }
    return buf[cnt];
}

inline int getint() {
    unsigned char c;
    do { c = rd(); }
    while (c == ' ' || c == '\n');
    int res = c - '0';
    while ((c=rd()) >= '0' && c <= '9') {
        res *= 10;
        res += c - '0';
    }
    return res;
}

実行結果

コード:

$ time ./getint < test2

real    0m0.748s
user    0m0.734s
sys     0m0.015s
$ time ./getint2 < test2

real    0m0.085s
user    0m0.046s
sys     0m0.015s

[cotora]

みけCAT様＞
ありがとうございます！
教えていただいたとおりnew[]を用いたところ、問題となっていたテストケースをパスすることができました。初期化についても指摘していただき、ありがとうございます。

YuO様＞
現在C++を勉強中です。C++だと，int A[n];およびint B[n];は不正、というのは知りませんでした。教えていただきありがとうございます！

あんどーなつ様＞
コードを上げていただきありがとうございます。scanfのほうが速いというのは私も最近知ったばかりなのですが、10倍も違うのですね。