動的計画法を用いて部分和問題を解きたいです。

Question

###前提・実現したいこと
このページの問題を解きたいです。
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3886

概要は、いくつかの個数の整数を要素に持つ集合があり、その中から適当な整数を選び出して和をとると、指定した値にできるかどうかを判定するという問題です。集合の要素の個数、集合の要素の値、目標値は全て自分で指定します。

実行例は以下の通りです。

//Sample Input
4                        // テストケース数
25                       // 和を25にしたい
4                        // 集合内にいくつの整数を要素として持つか
10 12 5 7                   // 集合内の4つの整数要素を指定
925                     // 和を925にしたい
10                          // 集合の要素数は10 
45 15 120 500 235 58 6 12 175 70    // 集合内の要素となる10個の整数
120                         // 以下繰り返し
5
25 25 25 25 25
0 
2
13 567

//Sample Output
NO      // その集合では和を25にできない
YES     // 和を925にできる
NO
YES

方針がわかりませんでしたが、いろいろ調べてみると以下のようなサイトを見つけたので、
ここに書いてある方針に倣い、動的計画法を使ってコードを書きました。
http://gushwell.ifdef.jp/etude/SubsetSum.html

###発生している問題・エラーメッセージ
コマンドプロンプト上で、上記のSample Input、並びにUDebug(https://www.udebug.com/UVa/12455)にある2つのInput例で試したところ、全く同じ結果が出力されました。
それにも関わらず、UVaでSubmitするとRuntime Errorとなってしまいます。

Runtime Errorについて調べたところ、「配列よりも大きな要素番号にアクセスしたり、ポインタの使用方法が間違っていたりして、セグメントエラーが発生することが主な原因」となるそうですが、もしそうだとしたら、コマンドプロンプト上で実行した時点で、結果が出力される前に何かしらのエラー文が出るのでは？と思いました。(自分はプログラミングができないので、十中八九この推測が違うんだろうとは思いますが)

せめてUVaが何行目でRuntime Errorとなったのか出してくれればいいのですが……
原因がまるで分らないので誰か助けてください……

###該当のソースコード

import java.util.StringTokenizer;
import java.io.*;

class Bars {
    public static void main (String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        try {
        	String line;
        	StringTokenizer token;
        	line = br.readLine();
        	int testcase = Integer.parseInt(line); // テストケース数

        	for(int a=0; a<testcase; a++) {  // テストケース数だけ一連の流れを繰り返す
        		line = br.readLine();
        		int target = Integer.parseInt(line);   // 目標値 和をこの値にできるかどうか
        		
        		if(target==0) System.out.println("YES");  
                         // 目標値が0なら空集合を取れば和を0にできるのでYES
        		else {
        			line = br.readLine();
        			int num = Integer.parseInt(line); // 集合の要素数
        		
        			int tmp;
        			int ex = 0;    // 目標値を超えた要素の値が来た時、ex(=exception)をインクリメント
        			int[] bar = new int[num]; // 要素数分の配列
        			line = br.readLine();
        			token = new StringTokenizer(line, " ");
        			
        			for(int i=0; i<num; i++) {
        				tmp = Integer.parseInt(token.nextToken());
        				if(tmp<=target) bar[i-ex] = tmp;  //要素が目標値より小さければ配列に入れる
        				else ex++;   // そうでない場合は配列に入れずにexをインクリメント
        			}            // 2行上でbar[i-ex]としているのは、例外が来ると要素数が減るため
        		
        			num -= ex;       // exの分だけ要素数が入力時よりも減る
        			
// この先は方針の参考にしたサイトに書いてある手順をコードにしました
        			int[] array = new int[target+1];  // 和が0～和がtarget → 大きさがtarget+1の配列
        			array[0] = 0;  // 配列の先頭には0、あとは全て-1を入れて初期化
        			for(int i=1; i<=target; i++) array[i] = -1;
        			boolean judge = false;   // 和がtargetになるとわかったらjudgeをtrueに書き換える

        			// nは参考サイトのnと同じ、jは同サイトにおけるi
        			for(int i=0; i<num; i++) {
        				int n = bar[i];
        				
        				for(int j=target; j>=0; j--) {
        					if(array[j]!=-1) {
        						if(n+j<=target && array[n+j]==-1) array[n+j] = n;
        					}
        				}
        				
       // array[target] (配列の最後)に-1以外が入った瞬間、それは和をtargetにできるということを意味する
        				if(array[target]!=-1) {
        					judge = true;
        					break;
        				}
        			}
        			
        			if(judge) System.out.println("YES");
        			else System.out.println("NO");
        		}
        	}
        
        } catch(IOException e) {
        		System.out.println("IOException" + e);
        		System.exit(1);
        }
	}
}

Answer 1

このコードでは目標数値が0である場合に、それに対応する集合要素の読み込みを行わず、
"Yes"を出力して次のテストケースを読み込むループに入ります。

この結果、その次の行の「集合の要素数」、さらに次の行の「集合の要素」を、
それぞれ次のループで「目標数値」、「集合の要素数」として読み込むことになります。
集合の要素としてスペース区切りとしている文字を要素数として変換しようとするため、
例外が発生してしまいます。

// 例として出ている入力において、最後のテストケースのあとにまだ続きがあったとしたら
0  //これがtargetに変換され、if(target==0)の判定でtrueになり、"Yes"を出力して次のループに移行
2  //次のループでこれがtargetに変換される 0ではないのでelseブロックへ
13 567  //集合の要素数numとしてこの文字列を変換しようとするが、変換できず例外発生

なので、目標数値が0でも、対応する要素数や集合の要素を全部ちゃんと読み込むようにする必要があります。

Comments

[RinT_hinabita39]

なるほど、Sample Inputの目標値が0のときに上手くいっていたのは、その後に何もなかったからですね… 無事Accepted頂きました！！本当にありがとうございます！！！！なんでそんなすぐ気付けるんですか…

[swordone]

デバッグではコンパイルも通り、テストケースでは問題なく出力される、しかし本番ではRuntimeError。
つまり、何か特定の条件で例外が発生しているということになります。
しかもIOExceptionではcatchされてしまうので、例外はRuntimeException系ということになります。
このコードで起こり得るそれは配列絡みかInteger.parseIntくらいしかないので、そこに絞り込んで考えたまでです。

[RinT_hinabita39]

なるほど、そういう論理立てになる訳ですね。まだプログラミングの経験と知識に乏しい自分にはなかなか厳しそうです… RuntimeException(実は初めて聞きました)やbinarySearchライブラリなど知らないこともいっぱい教えて下さり、それを自分で調べてみてへ～ってなってるので勉強の助けになってます。いつも本当にありがとうございます！！