配列 A,B を 1 オリジンにしないといけない理由を理解しないままコーディングし、その途中でインデックスがずれまくったために答えが合わず、無駄な時間を費やしてしまいました。また、A, B の配列のサイズを間違えていたため、Runtime Error を頻発させてしまいました。色々と申し訳ない感じに。。
#include <iostream> #include <vector> using namespace std; static void inputArray(int A[], int num) { for (int i = 0; i < num; i++) { cin >> A[i]; } } static void printArray(int A[], int num) { for (int i = 0; i < num; i++) { cout << ((i != 0) ? " " : "") << A[i]; } cout << endl; } static const int NMAX = 10000; static vector<int> C(NMAX + 1, 0); static inline void countingSort(int A[], int B[], int num) { for (int i = 0; i < num; i++) { C[A[i + 1]]++; } for (int i = 1; i <= NMAX; i++) { C[i] = C[i] + C[i - 1]; } // 前から検索すると安定ソートにはならない // for (int i = 1; i <= num; i++) { for (int i = num; i > 0; i--) { B[C[A[i]]] = A[i]; C[A[i]]--; } } static vector<int> A(2000000 + 1), B(2000000 + 1); int main() { int n; cin >> n; inputArray(&A[1], n); countingSort(&A[0], &B[0], n); printArray(&B[1], n); return 0; }