情報オリンピック予選　問題4

#1

開発環境はWindows Vista SP2、Dev-C++4.9.9.2、gcc3.4.2です。
問題文はhttp://www.ioi-jp.org/joi/2010/2011-yo-prob_and_sol/の問題4です。
自分が書いたプログラムで、１～４番目の入力に対しては正しい答えを出せましたが、
最後の入力のみ正しい答えが出せませんでした。
どこが間違っているか教えていただければ幸いです。
よろしくお願いします。

コード:

#include <stdio.h>

unsigned long long kazu[100][21];		/*そこからの種類数のキャッシュ*/
unsigned long long kazoe(int*,int,int,int);/*種類を数える関数*/

int main(int argc,char* argv[]) {
	char infile[255],outfile[255];
	FILE* in;
	FILE* out;
	/*declare values*/
	int suuzi[100];
	int kosuu;
	unsigned long long count;
	int i,j;
	/*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",&kosuu);				/*数字の個数を読み込む*/
	for(i=0;i<kosuu;i++) {				/*数字の個数繰り返す*/
		fscanf(in,"%d",&suuzi[i]);		/*数字を読み込む*/
		for(j=0;j<=20;j++)kazu[i][j]=-1;/*キャッシュを初期化*/
	}
	count=kazoe(suuzi,0,0,kosuu);		/*式の種類を数える*/
	fprintf(out,"%I64u\n",count);		/*式の種類を出力*/
	free(suuzi);
	/*file close*/
	fclose(in);
	fclose(out);
	return 0;
}

unsigned long long kazoe(int *suuzi,int now,int nowsum,int max) {
	unsigned long long sum=0,result;	/*式の種類*/
	int nowsuuzi;						/*ここまでの計算結果*/
	if(now==max-1) {					/*最後だったら*/
		if(nowsum==suuzi[now])return 1;	/*結果が一致していれば1*/
		else return 0;					/*違えば0*/
	}
	if(suuzi[now]!=0) {					/*今の数字が0でなければ*/
		nowsuuzi=nowsum+suuzi[now];		/*足してみる*/
		if(nowsuuzi>=0 && nowsuuzi<=20) {/*条件を満たしていれば*/
			if(kazu[now][nowsuuzi]==-1) {/*キャッシュがなければ*/
										/*式の種類を数える*/
				result=kazoe(suuzi,now+1,nowsuuzi,max);
										/*キャッシュを作成する*/
				kazu[now][nowsuuzi]=result;
			}
			sum+=kazu[now][nowsuuzi];	/*式の種類に加える*/
		}
		nowsuuzi=nowsum-suuzi[now];		/*引いてみる*/
		if(nowsuuzi>=0 && nowsuuzi<=20) {/*条件を満たしていれば*/
			if(kazu[now][nowsuuzi]==-1) {/*キャッシュがなければ*/
										/*式の種類を数える*/
				result=kazoe(suuzi,now+1,nowsuuzi,max);
										/*キャッシュを作成する*/
				kazu[now][nowsuuzi]=result;
			}
			sum+=kazu[now][nowsuuzi];	/*式の種類に加える*/
		}
	} else {							/*今の数字が0であれば*/
		if(kazu[now][nowsum]==-1) {		/*キャッシュがなければ*/
										/*式の種類を数える*/
										/*足しても引いても同じなので2倍*/
			result=kazoe(suuzi,now+1,nowsum,max)*2;
			kazu[now][nowsum]=result;	/*キャッシュを作成する*/
		}
		sum+=kazu[now][nowsum];			/*式の種類に加える*/
	}
	return sum;							/*ここまでの式の種類を返す*/
}

a5ua · #2

31行目の再帰関数呼び出しの初期値は、先頭の数字にしないとダメじゃないですか？

コード:

count=kazoe(suuzi,1,suuzi[0],kosuu);       /*式の種類を数える*/

あと、関係ないですが、33行目のfreeは不要だと思います。

たいちう · #3

随分時間が経ってしまったし、a5uaさんの回答で既に解決しているかな？

コード:

#include <iostream>
#include <fstream>
#include <string>
#include <ctime>
#include <windows.h>

using namespace std;

int number[100];
__int64 data[100][21];

__int64 calc(int index, int value) {
	if (value < 0 || 20 < value) return 0;

	if (data[index][value] < 0) {
		if (index == 0)
			data[0][value] = number[0] == value ? 1 : 0;
		else
			data[index][value] = calc(index - 1, value + number[index])
			                   + calc(index - 1, value - number[index]);
	}

	return data[index][value];
}

void solve(const string& fileName, __int64 expected) {
	DWORD t0 = ::GetTickCount();

	cout << fileName << endl;

	ifstream ifs(fileName.c_str());
	int length;
	ifs >> length;

	for (int i = 0; i < length; i++)
		ifs >> number[i];

	for (int i = 0; i < length; i++)
		for (int j = 0; j <= 20; j++)
			data[i][j] = -1;

	__int64 total = calc(length - 2, number[length - 1]);
	cout << total << " ... " << (total == expected ? "OK" : "NG") << endl;
	cout << "It took " << (::GetTickCount() % t0) / 1000. << " sec." << endl << endl;
}

int main() {
	solve("sample_1.txt", 10);
	solve("sample_2.txt", 7069052760);

	solve("input_1.txt", 488);
	solve("input_2.txt", 3443144);
	solve("input_3.txt", 1671496112);
	solve("input_4.txt", 31320243434344576);
	solve("input_5.txt", 671013170798012928);

	// quit
	cout << "End." << endl;
	cin.get();
	return 0;
}

#4

a5uaさん
うまく動きました。ありがとうございます。
他の入力では、最初に引いてしまうとマイナスになって無効と判定されるが、
最初が0だと無効にならずに2倍になってしまうようですね。
freeは単に配列を動的確保していた時の名残です。
解決にさせていただきます。

コード:

#include <stdio.h>

unsigned long long kazu[100][21];		/*そこからの種類数のキャッシュ*/
unsigned long long kazoe(int*,int,int,int);/*種類を数える関数*/

int main(int argc,char* argv[]) {
	char infile[255],outfile[255];
	FILE* in;
	FILE* out;
	/*declare values*/
	int suuzi[100];
	int kosuu;
	unsigned long long count;
	int i,j;
	/*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",&kosuu);				/*数字の個数を読み込む*/
	for(i=0;i<kosuu;i++) {				/*数字の個数繰り返す*/
		fscanf(in,"%d",&suuzi[i]);		/*数字を読み込む*/
		for(j=0;j<=20;j++)kazu[i][j]=-1;/*キャッシュを初期化*/
	}
	count=kazoe(suuzi,1,suuzi[0],kosuu);/*式の種類を数える*/
	fprintf(out,"%llu\n",count);		/*式の種類を出力*/
	/*file close*/
	fclose(in);
	fclose(out);
	return 0;
}

unsigned long long kazoe(int *suuzi,int now,int nowsum,int max) {
	unsigned long long sum=0,result;	/*式の種類*/
	int nowsuuzi;						/*ここまでの計算結果*/
	if(now==max-1) {					/*最後だったら*/
		if(nowsum==suuzi[now])return 1;	/*結果が一致していれば1*/
		else return 0;					/*違えば0*/
	}
	if(suuzi[now]!=0) {					/*今の数字が0でなければ*/
		nowsuuzi=nowsum+suuzi[now];		/*足してみる*/
		if(nowsuuzi>=0 && nowsuuzi<=20) {/*条件を満たしていれば*/
			if(kazu[now][nowsuuzi]==-1) {/*キャッシュがなければ*/
										/*式の種類を数える*/
				result=kazoe(suuzi,now+1,nowsuuzi,max);
										/*キャッシュを作成する*/
				kazu[now][nowsuuzi]=result;
			}
			sum+=kazu[now][nowsuuzi];	/*式の種類に加える*/
		}
		nowsuuzi=nowsum-suuzi[now];		/*引いてみる*/
		if(nowsuuzi>=0 && nowsuuzi<=20) {/*条件を満たしていれば*/
			if(kazu[now][nowsuuzi]==-1) {/*キャッシュがなければ*/
										/*式の種類を数える*/
				result=kazoe(suuzi,now+1,nowsuuzi,max);
										/*キャッシュを作成する*/
				kazu[now][nowsuuzi]=result;
			}
			sum+=kazu[now][nowsuuzi];	/*式の種類に加える*/
		}
	} else {							/*今の数字が0であれば*/
		if(kazu[now][nowsum]==-1) {		/*キャッシュがなければ*/
										/*式の種類を数える*/
										/*足しても引いても同じなので2倍*/
			result=kazoe(suuzi,now+1,nowsum,max)*2;
			kazu[now][nowsum]=result;	/*キャッシュを作成する*/
		}
		sum+=kazu[now][nowsum];			/*式の種類に加える*/
	}
	return sum;							/*ここまでの式の種類を返す*/
}

たいちうさん
すみません、C++はよくわからないです。
できればコメントを付けていただけますか？

たいちう · #5

ちょっと今忙しいので、何とか解読して、判らないところを聞いてください。
ファイルからの読み込みと解の表示以外は基本的にはCと同じです。

		4月 2024
日	月	火	水	木	金	土
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30