ここから本文です

aojの問題のプログラムを書いているのですが、下記のプログラムだとMemory Limit E...

nii********さん

2016/11/522:50:21

aojの問題のプログラムを書いているのですが、下記のプログラムだとMemory Limit Exceededが出てしまいます。何が問題かわかる方いれば教えて頂きたいです。問題はこちらになります。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_C&...


import java.util.Scanner;

class Card{
public String suit;
public int value;
}

public class Main{
public static void main(String[] args){
int i, q;
Card[] A = new Card[100000];
Card[] B = new Card[100000];
int stable = 1;

Scanner s = new Scanner(System.in);
int n = s.nextInt();

for(i=0; i<n; i++){
A[i] = new Card();
B[i] = new Card();
}

for(i=0; i<n; i++){
A[i].suit = B[i].suit = s.next();
A[i].value = B[i].value = s.nextInt();
}

mergeSort(B, n, 0, n);
quickSort(A, n, 0, n-1);

for(i=0; i<n; i++){
//マージソートとクイックソートの結果を比べる
if(A[i].suit != B[i].suit) stable = 0;
}

if(stable == 1){
System.out.print("Stable\n");
}else{
System.out.print("Not stable\n");
}
for(i=0; i<n; i++){
System.out.printf("%s %d\n", A[i].suit, A[i].value);

}
}

public static int partition(Card[] A, int n, int p, int r){
int x, i, j;
Card tmp;
x = A[r].value;
i = p-1;
for(j=p; j<r; j++){
if(A[j].value<=x){
i++;
tmp = A[i]; A[i] = A[j]; A[j] = tmp;
}
}
tmp = A[i+1]; A[i+1] = A[r]; A[r] = tmp;
return i+1;
}

public static void quickSort(Card[] A, int n, int p, int r){
int q;
if(p < r){
q = partition(A, n, p, r);
quickSort(A, n, p, q - 1);
quickSort(A, n, q + 1, r);
}
}

public static void merge(Card A[], int n, int left, int mid, int right){
int i, j, k;
int SENTINEL=2000000000;
Card[] L = new Card[100000 / 2+2];
Card[] R = new Card[100000 / 2+2];

for(i=0; i<n; i++){
L[i] = new Card();
R[i] = new Card();
}

int n1 = mid - left;
int n2 = right - mid;
for(i=0; i<n1; i++) L[i]= A[left + i];
for(i=0; i<n2; i++) R[i]= A[mid + i];
L[n1].value = R[n2].value = SENTINEL;
i = j = 0;
for(k=left; k<right; k++){
if(L[i].value <= R[j].value){
A[k] = L[i++];
}else{
A[k] = R[j++];
}
}
}
public static void mergeSort(Card A[], int n, int left, int right){
int mid;
if(left+1<right){
mid = (left + right) / 2;
mergeSort(A, n, left, mid);
mergeSort(A, n, mid, right);
merge(A, n, left, mid, right);
}
}
}

補足C言語での解答例
https://gyazo.com/9013469e2f655d07fa711584a2d264e1
https://gyazo.com/99277d7aa94d727b7397c0b83aa5dc6a

閲覧数:
86
回答数:
2
お礼:
500枚

違反報告

ベストアンサーに選ばれた回答

foo********さん

2016/11/609:22:11

質問文コード、問題 ともに、パッと見しただけですけど。

1. なぜ常に100000個?
配列(複数)にしろ、そこからポイントするCardオブジェクトにしろ、
固定数 100000 (とか 100000 / 2+2 などそこからの導出値)で
生成されてるけど、なぜ?

問題文みると カードの枚数n は入力で与えられるわけでしょ?
100000 でなく n でいいし、そうすべきでは?

2. なぜマージソート?
問題見ると、クィックソート。
なのになぜマージソートも行う?

stable/not stable の判断は、「マージソートの結果と比較」
しなくても、可。

問題が解けさえすればいいので、使う方法が手っ取り早くて
お安いものならなんでもいいわけでしょうけど、
マージソートのために別途 配列・オブジェクト 多数
使ってるよね?

Memory Limit Exceeded が直接お悩みなわけでしょ?
使わなくて済むように 減らす しかないと思うが。

  • 質問者

    nii********さん

    2016/11/610:13:54

    コメントありがとうございます。
    教科書に模範解答があり、その解答例をまんまjavaに翻訳した形なのですが、解答例ではマージソートと比較していたために真似しました。

    配列に10万で初期化しているのは、問題の制約に1<=n<=10万とあるからです。

    stable/not stableの判断を、マージソート以外で行うおおまかな方法を教えていただけますでしょうか。

  • その他の返信を表示

返信を取り消しますが
よろしいですか?

  • 取り消す
  • キャンセル

ベストアンサー以外の回答

1〜1件/1件中

sle********さん

2016/11/617:12:24

もしかすると10万個もインスタンス化すると負けかもしれない。
一つのカードデータは一つの整数で持つ。ビットフィールドを考える。
絵柄 : 4通り : 2-bit
カードに書かれる数 : 10の9乗通り : 30-bit
入力時順序 : 100000通り : 17-bit
計 49-bit なのでlongに収まる
https://codeiq.jp/magazine/2013/08/1748/

返信を取り消しますが
よろしいですか?

  • 取り消す
  • キャンセル

この質問につけられたタグ

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる