第10回 情報オリンピック 問題3

[学生A]

オセロとはまた別の話題で質問します。
今、第10回日本情報オリンピックの過去問　問3（http://www.ioi-jp.org/joi/2010/2011-yo- ... yo-t3.html）を解いてみたのですが、
このプログラムで入力1や入力2をinput.txtとして読み込んだ場合は、正常に機能するにもかかわらず
入力3,4,5を入れると「0x00f71646 でハンドルされていない例外が発生しました: 0xC0000005: 場所 0x00000000 に書き込み中にアクセス違反が発生しました。」
などというエラーが発生します。
このエラーはどのような原因で発生し、どのようにすれば修正できるのでしょうか。解答よろしくお願いします。

コード:

#include <stdio.h>
#include <stdlib.h>

//n=タイルの辺の数 , k=剥がれたタイルの数 , i=ループ用変数
int n,k,i;
//heap1=剥がれたタイルのx座標
//heap2=剥がれたタイルのy座標
//tile=剥がれる前のタイルの配列（1=赤 , 2=青 , 3=黄）
int *heap1;
int *heap2;
int *tile;


//デバッグ用。nとtileを出力する。
void debug(){
	printf("n=%d\n",n);
	for(i=0;i<n*n;i++) {
		if (i%n==0) printf("\n");
		printf("%d",tile[i]);
	}
	printf("\n");
}

//ここから始める
int main() {
	
	FILE *fp;

	fp = fopen( "input.txt", "r" );
	if( fp == NULL )
	{
		printf("input.txtが開けません！！");
		scanf("%d",&i);
		exit(0);
	}
	
	//入力からn,kを読み取る
	fscanf(fp,"%d",&n);
	fscanf(fp,"%d",&k);
	
	//n,kを基に動的配列を作成
	heap1=(int *)malloc(sizeof(int)*k);
	heap2=(int *)malloc(sizeof(int)*k);
	tile =(int *)malloc(sizeof(long)*n*n);

	if (heap1 == NULL) {exit(0);}
	if (heap2 == NULL) {exit(0);}
	
	//heapに剥がれたタイルのデーターを読み込む
	for(i=0; i<n && !feof(fp); i++) {
		fscanf(fp,"%d %d",heap1+i,heap2+i);
	}
	fclose(fp);

	//剥がれる前のタイルのデーターをtile配列に格納（変なアルゴリズムです…すいません。）
	for(i=0;i<n*n;i++) {
		//w=横 h=縦 j=縦横のうち小さい方
		int w,h,j;
		w=i%n;
		h=i/n;

		//w,hをn/2以下になるように対照的に変換
		if (w>n-w-1){w=n-w-1;}
		if (h>n-h-1){h=n-h-1;}

		//外辺に近い方をjに格納
		if (w<h) {j=w;} else {j=h;}

		//jによってtileを決める
		tile[(i/n)*n+(i%n)]=j%3+1;
	}
	
	//デバッグ用
	//debug();
	
	//剥がれたタイルの色の表示（1=赤 , 2=青 , 3=黄）
	for(i=0;i<k;i++) {
		printf("%d\n",tile[(heap2[i]-1)*n+(heap1[i]-1)]);
	}

	//入力待ち
	scanf("%d",&i);
	
	return 0;
}

*このプログラムは、http://www.ioi-jp.org/joi/2010/2011-yo- ... mlの問題3の入力1～5
に書いてる情報をローカルのinput.txtに書きこんでから使用してください。

[a5ua]

nが大きな値、たとえば n = 900000000のとき、n * nを計算すると、int型の範囲ではオーバーフローしてしまうため、正しい値となりません。
これを回避するには、アルゴリズムを変更する必要があります。
n * n の配列をつくらずとも、タイルの色は計算できるはずですので、考えてみてください。

[学生A]

a5uaさん、返信ありがとうございます。
なるほど、タイルの情報全てを配列に格納するのはオーバーフローするし、無駄ということですね。
プログラムを以下のように変えることによって、入力1～5全てで正しい答えを出力できるようになりました。
ありがとうございます！

コード:

#include <stdio.h>
#include <stdlib.h>

//n=タイルの辺の数 , k=剥がれたタイルの数 , i=ループ用変数
int n,k,i;
//heap1=剥がれたタイルのx座標
//heap2=剥がれたタイルのy座標
int *heap1;
int *heap2;

//ここから始める
int main() {
	
	FILE *fp;

	fp = fopen( "input.txt", "r" );
	if( fp == NULL )
	{
		printf("input.txtが開けません！！");
		scanf("%d",&i);
		exit(0);
	}
	
	//入力からn,kを読み取る
	fscanf(fp,"%d",&n);
	fscanf(fp,"%d",&k);
	
	//n,kを基に動的配列を作成
	heap1=(int *)malloc(sizeof(int)*k);
	heap2=(int *)malloc(sizeof(int)*k);

	if (heap1 == NULL) {exit(0);}
	if (heap2 == NULL) {exit(0);}
	
	//heapに剥がれたタイルのデーターを読み込む
	for(i=0; i<n && !feof(fp); i++) {
		fscanf(fp,"%d %d",heap1+i,heap2+i);
	}
	fclose(fp);

	//剥がれる前のタイルのデーターをtile配列に格納（変なアルゴリズムです…すいません。）
	for(i=0;i<k;i++) {
		//w=横 h=縦 j=縦横のうち小さい方
		int w,h,j;
		w=heap1[i]-1;
		h=heap2[i]-1;

		//w,hをn/2以下になるように対照的に変換
		if (w>n-w-1){w=n-w-1;}
		if (h>n-h-1){h=n-h-1;}

		//外辺に近い方をjに格納
		if (w<h) {j=w;} else {j=h;}

		//jによって色決定
		printf("%d\n",j%3+1);
	}

	//入力待ち
	scanf("%d",&i);
	
	return 0;
}

[学生A]

また解決チェック入れ忘れました・・・
すみません。

[たいちう]

この問題は解いた覚えがあったが、ソースも残っていた。
ご参考までに。

コード:

void solve(const string& fileName) {
	cout << fileName << endl;

	ifstream ifs(fileName.c_str());
	int edge, n;
	ifs >> edge >> n;

	ofstream ofs(string(fileName + "_a.txt").c_str());
	for (int i = 0; i < n; i++) {
		int x, y;
		ifs >> x >> y;
		if (x > edge + 1 - x)
			x = edge + 1 - x;
		if (y > edge + 1 - y)
			y = edge + 1 - y;
		if (x > y)
			x = y;
		cout << ((x - 1) % 3 + 1) << endl;
		ofs << ((x - 1) % 3 + 1) << endl;
	}
}

[みけCAT]

自分が書いたソースコードもありました。
一応載せてみます。

コード:

#include <stdio.h>

int main(int argc,char* argv[]) {
	char infile[255],outfile[255];
	FILE* in;
	FILE* out;
	/*declare values*/
	int n,k;
	int x,y;
	int i;
	/*open files*/
	sprintf(infile,"%s-in%s.txt",argv[1],argv[2]);
	sprintf(outfile,"%s-out%s.txt",argv[1],argv[2]);
	in=fopen(infile,"r");
	if(in==NULL)return 1;
	out=fopen(outfile,"w");
	if(out==NULL) {
		fclose(in);
		return 1;
	}
	/*do work*/
	fscanf(in,"%d",&n);
	fscanf(in,"%d",&k);
	for(i=0;i<k;i++) {
		fscanf(in,"%d %d",&x,&y);
		if(x*2>n)x=n-x+1;
		if(y*2>n)y=n-y+1;
		if(x>y)fprintf(out,"%d\n",(y-1)%3+1);
		else fprintf(out,"%d\n",(x-1)%3+1);
	}
	/*file close*/
	fclose(in);
	fclose(out);
	return 0;
}

[学生A]

＞たいちうさん
おお、なるほど。c++言語で書くとこんなにスマートに書けるんですね。
特にファイルからの情報の読み取り方は参考になりました。
ありがとうございます。

＞みけCATさん

コード:

        if(x*2>n)x=n-x+1;
        if(y*2>n)y=n-y+1;

なるほど。感心してしまいました。

二人のソースを見ると如何に自分が無駄なことをしていたのかに気付かされました。
特に、heapはfor文中に読み込むことによって、完全に要らない物になるのには驚きました！
これからもプログラミングに励みます。どうぞよろしくお願いします。