c++ ランタイムエラーが吐かれる

Question

paizaの問題であみだくじを与えられたときに一番左はじにたどり着くくじはどれかを解答する問題で以下のようなコードを書きました.しかし提出すると10個あるテストケースのうち3つのテストケースでランタイムエラーが出されました.どの部分がエラーを出しているかわからないのでわかる方いたらご教授お願いします.
入力は次のように与えられます.
L n m L = くじの長さ(cm) n = くじの本数 m = くじを繋ぐ横線の本数
ai bi ci ai = 左から何番目のくじか表す bi = 上からbi(cm)の位置にai番目のくじから線を引く
・ ・ ・ ci = 上からci(cm)の位置にai+1番目のくじに線を引く
・ ・ ・
・ ・ ・

あみだくじの横線が入るところをcountで対応させそれ以外を0にして
あとは左下からくじを辿っていく形にしています.
エラー箇所がわかりましたらお願いします
#include <iostream>
#include <stdio.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdio>
#include <utility>
#include <sstream>

using namespace std;

int main(){
int L, n, m;
cin >> L >> n >> m;
int amida[L][n];
for(int i = 0;i < L;i++){
for(int j = 0;j < n;j++){
amida[i][j] = 0;
}
}

int a, b, c;
int count = 1;
while(cin >> a >> b >> c){
	//cout << "a = " << a << " b = " << b << " c = " << c << endl;
	amida[b-1][a-1] = count;
	amida[c-1][a] = -1*count;
	count++;
}

int x = 0, y = 0, temp = 0;
int p = 0, hantei = 0;
for(int i = 0;i < L;i++){
	if(amida[i][0] != 0){
		temp = amida[i][0];
	}
}
//cout << temp << endl;
while(1){
	if(temp == 0) break;
	else if(temp > 0){
		for(int i = 0;i < L;i++){
			//cout << "amida[i][x+1] = " << amida[i][x+1] << endl;
			if(abs(temp) == abs(amida[i][p+1])){
				x = p + 1;
				p++;
				y = i;
				break;
			}
		}
		//cout << "x = " << x << " y = " << y << endl;
		for(int i = y-1;i >= 0;i--){
			if(amida[i][x] != 0){
				temp = amida[i][x];
				break;
			}
			if(i == 0) y = 0;
		}
	}
	if(y == 0) break;
	else if(temp < 0){
		for(int i = 0;i < L;i++){
			if(abs(temp) == abs(amida[i][p-1])){
				x = p - 1;
				p--;
				y = i;
				break;
			}
		}
		for(int i = y-1;i >= 0;i--){
			if(amida[i][x] != 0){
				temp = amida[i][x];
				break;
			}
			if(i == 0) y = 0;
		}
	}
	
	if(y == 0) break;
}
cout << x+1 << endl;
return 0;

}

Comments

[Chironian]

エラーのでるテストケースを記載すると良いですよ。
ああ、ビルドできないですね。int L, n, m; ... ; int amida[L][n];はC/C++ではできません。

[takehisa555]

テストケースに用いられている入力の値は参照できないので値がわからないんですよね(汗)失敗したテストケースには条件内の特殊なデータ, 大規模データとしか書いてないです

Answer 1

こんにちは。

ところで、ソースをざっとみてみましたが、複雑で読み取れませんでした。
横線に番号が振ってあったり正や負があったり、私の知っているあみだくじとは異なるルールなのかも？

となると、テストケースがないと厳しいですね。
テストケースが開示されないのは辛いところですが、回答者側で見出すのは厳しいと思います。
takkeshanさん自身で落ちるケースを見つけることはできませんか？

Comments

[takehisa555]

なんとかエラーのケースを探してみます.
コードが複雑なのは初心者なもので冗長にしか書けないんです・・・
勉強します((+_+))

書きたかったことは
1. 横線に番号振ってどこからどこへ向かうのかを対応させる.(正負は正だと横線を右に向かい, 負だと左に向かうなど向きを示している)
2. while文の前に見つけた左下が初めにぶつかる横線から順に上をみていきその都度xとyに座標(配列のインデックス)を更新していく
3. 移動した先の配列の上が全部0ならwhile文を抜けそのときのxが答えとなる
って流れです.

[Chironian]

> 1. 横線に番号振ってどこからどこへ向かうのかを対応させる.

countは単純に入力順でカウントアップされているので、「どこからどこへ」を示していないように思います。

> (正負は正だと横線を右に向かい, 負だと左に向かうなど向きを示している)

なるほど、クジを中心にそこから出ている横線を右と左で表現しているのですね。
例えば、クジを中心にそこから右へ出ている横線だけで表現できませんか？つまり、左へ出ている横線は左隣のクジに設定するわけです。恐らく単純化できると思いますよ。

> 2. while文の前に見つけた左下が初めにぶつかる横線から順に上をみていきその都度xとyに座標(配列のインデックス)を更新していく

この辺が読み取れません。あみだくじを追いかける時って指で押さえて上に向かって移動し、横線があったら辿りますよね。それと同じ処理ではダメですか？
takkeshanさんが表現しているように(x, y)で現在の指の位置とするのは良いと思いますよ。最初は左下なのでたぶん(0, L-1)ですね。「(x, y)に横線がつながっていたらxを移動し、--y」をy==0になるまで繰り返しではどうでしょうか？

0開始か1開始には要注意です。L, m, nとa, b, cの値の範囲、たぶん出題にかかれているのでは？それによってどうするべきか決まると思います。

あ、後、mを使ってないですね。a, b, cの３つ組で入力されるのが違和感です。横線の本数は偶数になるのですね？

[takehisa555]

散々教えてもらってありがとうございました。
結局配列のメモリが足りなくてエラーを吐いていて
vectorにしたらうまく通りました！
最大値の時にどうやら不具合があったみたいです・・・

初歩的なミスでした。
ありがとうございました。
勉強します。

[Chironian]

なるほど。
可変長配列は恐らくスタック上にメモリを確保するので、スタックオーバーフローが起きたのですね。ということは、環境依存なのでよく見つけましたね！！ お疲れ様です。

Answer 2

paizaはテストケースが公開されないので想定が難しいと思いますが、特殊解などが失敗する場合は、境界値の問題に失敗している事が多いです。次の場合を想定してみてください。

• L, n, mがそれぞれ最小値のパターン、および、最大値のパターン
• 一本も横線を通らない
• 毎回横軸を通る(どんどん右に行くパターンと1番と2番を繰り返すパターンの二つ)
• 上からの位置(ci)が同じところに、横線が複数ある(別の縦線同士ならあり得ますよね？)

などなどです。とくに分岐しているような所を通るパターンを試すといいかと思います。

---

おまけ

可変長配列(VLA)を使っているようですが、C++の規格には本来無い機能です。Clang(paizaはこれらしい)やGCCでは独自拡張により問題なく使えてしまいますが、C++ではあまり使わない方がいいでしょう。代わりにstd::vector等を使うことをお勧めします。なお、Cなら規格で定められていますので、使っても問題ないです。可変長配列が使えないVisual Studioユーザが何か言ってきても、かわいそうな目でみてはいけません。

Comments

[Chironian]

あう、いつの間にか可変長配列なんてできてたのですね。なるほど。
gcc(MinGW)も使ってますので、どうぞ可哀想な目では見ないで下さいね。
確かにビルドできました！！いやビックリ。

[raccy]

> Chironianさん
(-д-).oO(C99の時からあるのに・・ｶｲｿｽ

[Chironian]

うぅぅ．．．

[yumetodo]

可変長配列はC++に何度も提案されてはrejectを食らってる機能でC言語使い曰くC99最大の失敗、と。

[raccy]

> C++に何度も提案されてはrejectを食らってる機能
C11ではオプションに格下げですし、でも、めげずにC++17にも提案中らしいですよ。
ぶっちゃけ、C++ならnew演算子で配列だと意識してメモリ確保できるし、どうしてもスタックに積みたい(関数抜けると自動で削除されたい)なら普通にstd::vectorとか使った方が綺麗に書けるし、必要性は感じないですけどね。むしろCにGoのスライスみたいのが欲しい。

[yumetodo]

>C11ではオプションに格下げですし

ほう、それは知らなかった。

可変長配列はスタック消費するので、いっそallocaを標準に入れるほうがまだよかった。
挙げ句GCCは
void f( size_t size )
{
struct
{
char a[size] ; // GCC拡張
} s ;
}
VLAIS(Variable length arrays in structs)という醜悪な拡張があり・・・

>CにGoのスライスみたいのが欲しい。
boostに1.56まであったんですけどね、あれどこ行ったんだ。change logでは見つからない
http://www.boost.org/doc/libs/1_56_0/libs/numeric/ublas/doc/range.htm

Answer 3

入力したあみだくじの数値が、０行のところまで値が入っているのが気になります。
０行をゴールとするのであれば、１行目から値を入力するという方法を試してはいかがですか？

例
０行目 0 -1 0 0
↓
０行目 0 0 0 0
１行目 0-1 0 0