第10回日本情報オリンピック予選 問題６

[みけCAT]

http://www.ioi-jp.org/joi/2010/2011-yo- ... index.html
の問題６をやっています。
解説の解法３を使おうとしているのですが、実行速度が遅いです。
線形探索版は入力３まで、連想配列版は入力２までしか答えを出せませんでした。
どうすればうまく解けるか教えていただければありがたいです。
C言語の範囲（Ｃ＋＋は使わない）でお願いします。
よろしくお願いします。

線形探索版

コード:

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

#define nizi(c,x,y) (c[(y)*20+(x)])
#define c2m(c) ((c)=='J'?0:(c)=='O'?1:(c)=='I'?2:3)

typedef struct {
	int max[4];
	int puttern[4][11000];
	int kosuu[4][11000];
} memoone;

memoone* memo;

int countflags(char[21][21],int,int,int,int,int);

int main(int argc,char* argv[]) {
	char infile[255],outfile[255];
	FILE* in;
	FILE* out;
	/*declare values*/
	int tate,yoko;
	char map[21][21];
	int i;
	int x,y;
	int allflags;
	int badflags;
	int goodflags;
	/*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*/
	memo=calloc(20*21,sizeof(memoone));
	if(memo==NULL)return 1;
	fscanf(in,"%d %d",&tate,&yoko);
	for(i=1;i<=tate;i++)fscanf(in,"%s",map[i]);
	allflags=1;
	for(y=1;y<=tate;y++) {
		for(x=0;x<yoko;x++) {
			if(map[y][x]=='?')allflags=allflags*3%100000;
		}
	}
	strcpy(map[0],"IIIIIIIIIIIIIIIIIIII");
	badflags=countflags(map,0,1,0,yoko,tate+1);
	goodflags=allflags-badflags;
	if(goodflags<0)goodflags+=100000;
	fprintf(out,"%d\n",goodflags);
	free(memo);
	/*file close*/
	fclose(in);
	fclose(out);
	return 0;
}

int searchputtern(int x,int y,int mozi,int puttern) {
	int i;
	for(i=0;i<nizi(memo,x,y).max[mozi];i++) {
		if(nizi(memo,x,y).puttern[mozi][i]==puttern)return i;
	}
	return -1;
}

int countflags(char map[21][21],int x,int y,int maeputtern,int mx,int my) {
	int i;
	int nowputtern;
	int ptno;
	int results;
	int nextx,nexty;
	nowputtern=maeputtern>>1;
	nowputtern&=~(((x>1?(map[y][x-1]=='O'):x>0?0:(map[y-1][mx-1]=='O'))?0:1)<<(mx-2));
	if(x>0 && map[y][x-1]=='J')nowputtern|=1<<(mx-1);
	ptno=searchputtern(x,y,c2m(map[y][x]),nowputtern);
	if(ptno>=0)return nizi(memo,x,y).kosuu[c2m(map[y][x])][ptno];
	results=0;
	if(x<mx-1) {
		nextx=x+1;
		nexty=y;
	} else {
		nextx=0;
		nexty=y+1;
	}
	if(nexty<my) {
		if(map[y][x]!='?') {
			if(map[y-1][x]=='J' && map[y-1][x+1]=='O' && map[y][x]=='I')results=0;
			else results=countflags(map,nextx,nexty,nowputtern,mx,my);
		} else {
			map[y][x]='J';
			results+=countflags(map,nextx,nexty,nowputtern,mx,my);
			map[y][x]='O';
			results+=countflags(map,nextx,nexty,nowputtern,mx,my);
			if(map[y-1][x]!='J' || map[y-1][x+1]!='O') {
				map[y][x]='I';
				results+=countflags(map,nextx,nexty,nowputtern,mx,my);
			}
			map[y][x]='?';
		}
	} else {
		switch(map[y][x]) {
			case 'J':
				results=1;
				break;
			case 'O':
				results=1;
				break;
			case 'I':
				if(map[y-1][x]!='J' || map[y-1][x+1]!='O')results=1;
				break;
			case '?':
				results=2;
				if(map[y-1][x]!='J' || map[y-1][x+1]!='O')results++;
				break;
		}
	}
	nizi(memo,x,y).puttern[c2m(map[y][x])]
		[nizi(memo,x,y).max[c2m(map[y][x])]]=nowputtern;
	nizi(memo,x,y).kosuu[c2m(map[y][x])]
		[nizi(memo,x,y).max[c2m(map[y][x])]]=results%100000;
	nizi(memo,x,y).max[c2m(map[y][x])]++;
	return results%100000;
}

連想配列版

コード:

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

#define nizi(c,x,y) (c[(y)*20+(x)])
#define c2m(c) ((c)=='J'?0:(c)=='O'?1:(c)=='I'?2:3)

typedef struct {
	int puttern[4][11000];
	int kosuu[4][11000];
	int used[4][11000];
} memoone;

memoone* memo;

int countflags(char[21][21],int,int,int,int,int);

int main(int argc,char* argv[]) {
	char infile[255],outfile[255];
	FILE* in;
	FILE* out;
	/*declare values*/
	int tate,yoko;
	char map[21][21];
	int i;
	int x,y;
	int allflags;
	int badflags;
	int goodflags;
	/*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*/
	memo=calloc(20*21,sizeof(memoone));
	if(memo==NULL)return 1;
	fscanf(in,"%d %d",&tate,&yoko);
	for(i=1;i<=tate;i++)fscanf(in,"%s",map[i]);
	allflags=1;
	for(y=1;y<=tate;y++) {
		for(x=0;x<yoko;x++) {
			if(map[y][x]=='?')allflags=allflags*3%100000;
		}
	}
	strcpy(map[0],"IIIIIIIIIIIIIIIIIIII");
	badflags=countflags(map,0,1,0,yoko,tate+1);
	goodflags=allflags-badflags;
	if(goodflags<0)goodflags+=100000;
	fprintf(out,"%d\n",goodflags);
	free(memo);
	/*file close*/
	fclose(in);
	fclose(out);
	return 0;
}

int searchputtern(int x,int y,int mozi,int puttern) {
	int i;
	i=puttern%11000;
	while(1) {
		if(nizi(memo,x,y).used[mozi][i] &&
			nizi(memo,x,y).puttern[mozi][i]==puttern)return i;
		else if(nizi(memo,x,y).used[mozi][i]==0)return -1;
		i=(i+123)%11000;
	}
	return -1;
}

int countflags(char map[21][21],int x,int y,int maeputtern,int mx,int my) {
	int i;
	int nowputtern;
	int ptno;
	int results;
	int nextx,nexty;
	int index;
	nowputtern=maeputtern>>1;
	nowputtern&=~(((x>1?(map[y][x-1]=='O'):x>0?0:(map[y-1][mx-1]=='O'))?0:1)<<(mx-2));
	if(x>0 && map[y][x-1]=='J')nowputtern|=1<<(mx-1);
	ptno=searchputtern(x,y,c2m(map[y][x]),nowputtern);
	if(ptno>=0)return nizi(memo,x,y).kosuu[c2m(map[y][x])][ptno];
	results=0;
	if(x<mx-1) {
		nextx=x+1;
		nexty=y;
	} else {
		nextx=0;
		nexty=y+1;
	}
	if(nexty<my) {
		if(map[y][x]!='?') {
			if(map[y-1][x]=='J' && map[y-1][x+1]=='O' && map[y][x]=='I')results=0;
			else results=countflags(map,nextx,nexty,nowputtern,mx,my);
		} else {
			map[y][x]='J';
			results+=countflags(map,nextx,nexty,nowputtern,mx,my);
			map[y][x]='O';
			results+=countflags(map,nextx,nexty,nowputtern,mx,my);
			if(map[y-1][x]!='J' || map[y-1][x+1]!='O') {
				map[y][x]='I';
				results+=countflags(map,nextx,nexty,nowputtern,mx,my);
			}
			map[y][x]='?';
		}
	} else {
		switch(map[y][x]) {
			case 'J':
				results=1;
				break;
			case 'O':
				results=1;
				break;
			case 'I':
				if(map[y-1][x]!='J' || map[y-1][x+1]!='O')results=1;
				break;
			case '?':
				results=2;
				if(map[y-1][x]!='J' || map[y-1][x+1]!='O')results++;
				break;
		}
	}
	index=nowputtern%11000;
	while(1) {
		if(nizi(memo,x,y).used[c2m(map[y][x])][index]==0)break;
		index=(index+123)%11000;
	}
	nizi(memo,x,y).puttern[c2m(map[y][x])][index]=nowputtern;
	nizi(memo,x,y).kosuu[c2m(map[y][x])][index]=results%100000;
	nizi(memo,x,y).used[c2m(map[y][x])][index]=1;
	return results%100000;
}

[たいちう]

> C言語の範囲（Ｃ＋＋は使わない）でお願いします。
> よろしくお願いします。

前回の質問同様に、C++のコードなら書きました。
アルゴリズムはCと変わらないと思いますので、
リクエストがあれば載せます。

[みけCAT]

「Ｃ＋＋は使わないで」というのは、
Ｃ＋＋でしか使えないクラス、たとえばstringやvectorなどを使ってほしくないという意味です。
前回の質問同様に入出力くらいならかまいません。
そうでなくても、参考にしたいので載せていただければありがたいです。

[たいちう]

map<int, map<int, int> > tableについてだけ説明します。
int table[j];
のように二次元配列として使えるものと思ってください。
48行目でデータがあればそれを使い、
データがなければ再帰呼び出し後に次回必要になった時のためにtableに入れます。

コード:

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

using namespace std;

char data[20][20];
int width, height;
map<int, map<int, int> > table;

int calc(int index) {
	if (index == width * height) return 1;

	static const char letter[] = { 'J', 'O', 'I' };

	int x = index % width;
	int y = index / width;

	char c0 = data[x][y];
	int ret = 0;
	for (int i = 0; i < 3; i++) {
		if (index == 1) {
			index = index;
		}
		if (c0 && c0 != letter[i]) continue;
		data[x][y] = letter[i];

		char buf[128] = { 0 };
		int j = 0;
		for (int k = index - width; k <= index; k++) {
			if (k < 0)
				buf[j++] = '_';
			else {
				buf[j++] = data[k % width][k / width];
				if (k % width == width - 1 && k != index)
					buf[j++] = '.';
			}
		}

		int bitmap = 0;
		for (int k = 0; k + 1 < j; k++)
			if (buf[k] == 'J' && buf[k + 1] == 'O')
				bitmap |= 1 << k;
		bitmap = (bitmap << 2) | i;

		if (table.find(index) != table.end() && table[index].find(bitmap) != table[index].end())
			ret += table[index][bitmap];
		else {
			if (data[x][y] == 'I' && 0 <= y - 1 && x + 1 < width &&
				data[x][y - 1] == 'J' && data[x + 1][y - 1] == 'O')
				;
			else {
				int value = calc(index + 1);
				table[index][bitmap] = value;
				ret += value;
			}
		}
	}
	data[x][y] = c0;
	return ret % 100000;
}

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

	cout << fileName << endl;

	ifstream ifs(fileName.c_str());

	ifs >> height >> width;
	string buf;
	getline(ifs, buf);

	int blank = 0;
	for (int y = 0; y < height; y++) {
		getline(ifs, buf);
		for (int x = 0; x < width; x++) {
			if (buf[x] == '?') {
				data[x][y] = 0;
				blank++;
			} else
				data[x][y] = buf[x];
		}
	}

	table.clear();

	int ng = calc(0);

	int total = blank ? 1 : 0;
	for (int i = 0; i < blank; i++) {
		total = (total * 3) % 100000;
	}

	int answer = (100000 + total - ng) % 100000;

	cout << answer;
	if (expected)
		cout << " ... " << (answer == expected ? "OK" : "NG");
	cout << endl;
	cout << "It took " << (::GetTickCount() % t0) / 1000. << " sec." << endl << endl;
}

int main() {
	solve("sample_1.txt",     4);
	solve("sample_2.txt",     3);
	solve("sample_3.txt",    53);
	solve("sample_4.txt", 28218);

	solve("input_1.txt",  3726);
	solve("input_2.txt", 19733);
	solve("input_3.txt", 30451);
	solve("input_4.txt", 48949);
	solve("input_5.txt", 90227);

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

[みけCAT]

table.findですか...
この検索の処理が一番知りたいところなのですが...

[たいちう]

std::mapは連想配列というものです。
これを自分で実装するためには、赤黒木について調べてみると良いでしょう。
アルゴリズムの勉強にはなりますよ。

[みけCAT]

http://www.geocities.jp/h2fujimura/mutt ... -tree.html
を参考に赤黒木を実装してみたのですが、やはり遅く、３番目までしか出力を得られません。
どうすればいいでしょうか？
また、赤黒木の実装はこれでいいでしょうか？
お願いします。
[tabs][tabs:赤黒木のみのテスト]

コード:

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

typedef struct _node {
	int puttern;
	int kosuu;
	int isred;
	struct _node* up;
	struct _node* left;
	struct _node* right;
} node;

node* root=NULL;

void rotate(node** taisyou,int isleft) {
	node* taisyouleft;
	node* taisyouright;
	node* taisyouup;
	int parentisleft;
	taisyouleft=(*taisyou)->left;
	taisyouright=(*taisyou)->right;
	taisyouup=(*taisyou)->up;
	if(taisyouup==NULL)parentisleft=0;
	else if(*taisyou==taisyouup->left)parentisleft=1;
	else parentisleft=-1;
	if(isleft) {
		(*taisyou)->right=taisyouright?taisyouright->left:NULL;
		if(taisyouright) {
			if(taisyouright->left)taisyouright->left->up=*taisyou;
			taisyouright->left=*taisyou;
			taisyouright->up=taisyouup;
		}
		if(*taisyou)(*taisyou)->up=taisyouright;
		*taisyou=taisyouright;
	} else {
		(*taisyou)->left=taisyouleft?taisyouleft->right:NULL;
		if(taisyouleft) {
			if(taisyouleft->right)taisyouleft->right->up=*taisyou;
			taisyouleft->right=*taisyou;
			taisyouleft->up=taisyouup;
		}
		if(*taisyou)(*taisyou)->up=taisyouleft;
		*taisyou=taisyouleft;
	}
	if(parentisleft==1)taisyouup->left=*taisyou;
	else if(parentisleft==-1)taisyouup->right=*taisyou;
}

int islefthantei(node* me) {
	if(me->up==NULL)return 0;
	if(me->up->left==me)return 1;
	return -1;
}

node* gettonari(node* me) {
	if(me->up==NULL)return NULL;
	if(islefthantei(me))return me->up->right;
	return me->up->left;
}

void chouseicolor(node* taisyou) {
	node* taisyouup;
	node* tonari;
	taisyouup=taisyou->up;
	if(taisyouup==NULL) {/*根なら色を黒に*/
		taisyou->isred=0;
		return;
	}
	if(taisyouup->isred==0)return;/*親が黒なら調整しない*/
	tonari=gettonari(taisyouup);
	if(tonari && tonari->isred) {/*隣が赤なら*/
		taisyouup->isred=0;
		tonari->isred=0;
		taisyouup->up->isred=1;
		chouseicolor(taisyouup->up);/*再帰的に調整する*/
	} else {
		if(islefthantei(taisyou)*islefthantei(taisyouup)<0) {
			/*内側にあったら*/
			if(islefthantei(taisyou)==1) {
				rotate(&taisyouup,0);
				taisyou=taisyou->right;
			} else {
				rotate(&taisyouup,1);
				taisyou=taisyou->left;
			}
		}
		if(islefthantei(taisyouup)==1) {
			rotate(&(taisyouup->up),0);
			taisyouup->isred=0;
			if(taisyouup->right)taisyouup->right->isred=1;
		} else if(islefthantei(taisyouup)==-1) {
			rotate(&(taisyouup->up),1);
			taisyouup->isred=0;
			if(taisyouup->left)taisyouup->left->isred=1;
		}
	}
}

void insert(int puttern,int kosuu) {
	node* insertfor;
	node* nextinsertfor;
	/*挿入位置を探索*/
	insertfor=NULL;
	nextinsertfor=root;
	while(nextinsertfor) {
		insertfor=nextinsertfor;
		if(puttern<insertfor->puttern)nextinsertfor=insertfor->left;
		else nextinsertfor=insertfor->right;
	}
	/*挿入*/
	nextinsertfor=calloc(1,sizeof(node));
	nextinsertfor->puttern=puttern;
	nextinsertfor->kosuu=kosuu;
	nextinsertfor->isred=1;
	nextinsertfor->up=insertfor;
	if(root==NULL)root=nextinsertfor;
	else {
		if(puttern<insertfor->puttern)insertfor->left=nextinsertfor;
		else insertfor->right=nextinsertfor;
	}
	/*色の調整*/
	chouseicolor(nextinsertfor);
}

int search(int puttern) {
	node* current;
	current=root;
	while(current) {
		if(current->puttern==puttern)return current->kosuu;
		if(puttern<current->puttern)current=current->left;
		else current=current->right;
	}
	return -1;
}

void _freetree(node** taisyou) {
	if(*taisyou==NULL)return;
	_freetree(&((*taisyou)->left));
	_freetree(&((*taisyou)->right));
	free(*taisyou);
	*taisyou=NULL;
}

void freetree() {
	_freetree(&root);
}

int main(void) {
	int puttern;
	int kosuu;
	while(1) {
		printf("パターンを入力してください。\n");
		printf("やめる場合は-1を入力してください。\n>");
		scanf("%d",&puttern);
		if(puttern<0)break;
		kosuu=search(puttern);
		if(kosuu!=-1)printf("個数は%dです。\n",kosuu);
		else {
			do {
				printf("負でない個数を入力してください。\n>");
				scanf("%d",&kosuu);
			} while(kosuu<0);
			insert(puttern,kosuu);
		} 
	}
	freetree();
	return 0;
}

[tabs:実際に使用したコード]

コード:

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

#define nizi(c,x,y) (c[(y)*20+(x)])
#define c2m(c) ((c)=='J'?0:(c)=='O'?1:(c)=='I'?2:3)


typedef struct _node {
	int puttern;
	int kosuu;
	int isred;
	struct _node* up;
	struct _node* left;
	struct _node* right;
} node;

void rotate(node** taisyou,int isleft) {
	node* taisyouleft;
	node* taisyouright;
	node* taisyouup;
	int parentisleft;
	taisyouleft=(*taisyou)->left;
	taisyouright=(*taisyou)->right;
	taisyouup=(*taisyou)->up;
	if(taisyouup==NULL)parentisleft=0;
	else if(*taisyou==taisyouup->left)parentisleft=1;
	else parentisleft=-1;
	if(isleft) {
		(*taisyou)->right=taisyouright?taisyouright->left:NULL;
		if(taisyouright) {
			if(taisyouright->left)taisyouright->left->up=*taisyou;
			taisyouright->left=*taisyou;
			taisyouright->up=taisyouup;
		}
		if(*taisyou)(*taisyou)->up=taisyouright;
		*taisyou=taisyouright;
	} else {
		(*taisyou)->left=taisyouleft?taisyouleft->right:NULL;
		if(taisyouleft) {
			if(taisyouleft->right)taisyouleft->right->up=*taisyou;
			taisyouleft->right=*taisyou;
			taisyouleft->up=taisyouup;
		}
		if(*taisyou)(*taisyou)->up=taisyouleft;
		*taisyou=taisyouleft;
	}
	if(parentisleft==1)taisyouup->left=*taisyou;
	else if(parentisleft==-1)taisyouup->right=*taisyou;
}

int islefthantei(node* me) {
	if(me->up==NULL)return 0;
	if(me->up->left==me)return 1;
	return -1;
}

node* gettonari(node* me) {
	if(me->up==NULL)return NULL;
	if(islefthantei(me))return me->up->right;
	return me->up->left;
}

void chouseicolor(node* taisyou) {
	node* taisyouup;
	node* tonari;
	taisyouup=taisyou->up;
	if(taisyouup==NULL) {/*根なら色を黒に*/
		taisyou->isred=0;
		return;
	}
	if(taisyouup->isred==0)return;/*親が黒なら調整しない*/
	tonari=gettonari(taisyouup);
	if(tonari && tonari->isred) {/*隣が赤なら*/
		taisyouup->isred=0;
		tonari->isred=0;
		taisyouup->up->isred=1;
		chouseicolor(taisyouup->up);/*再帰的に調整する*/
	} else {
		if(islefthantei(taisyou)*islefthantei(taisyouup)<0) {
			/*内側にあったら*/
			if(islefthantei(taisyou)==1) {
				rotate(&taisyouup,0);
				taisyou=taisyou->right;
			} else {
				rotate(&taisyouup,1);
				taisyou=taisyou->left;
			}
		}
		if(islefthantei(taisyouup)==1) {
			rotate(&(taisyouup->up),0);
			taisyouup->isred=0;
			if(taisyouup->right)taisyouup->right->isred=1;
		} else if(islefthantei(taisyouup)==-1) {
			rotate(&(taisyouup->up),1);
			taisyouup->isred=0;
			if(taisyouup->left)taisyouup->left->isred=1;
		}
	}
}

void insert(node** root,int puttern,int kosuu) {
	node* insertfor;
	node* nextinsertfor;
	/*挿入位置を探索*/
	insertfor=NULL;
	nextinsertfor=*root;
	while(nextinsertfor) {
		insertfor=nextinsertfor;
		if(puttern<insertfor->puttern)nextinsertfor=insertfor->left;
		else nextinsertfor=insertfor->right;
	}
	/*挿入*/
	nextinsertfor=calloc(1,sizeof(node));
	nextinsertfor->puttern=puttern;
	nextinsertfor->kosuu=kosuu;
	nextinsertfor->isred=1;
	nextinsertfor->up=insertfor;
	if(*root==NULL)*root=nextinsertfor;
	else {
		if(puttern<insertfor->puttern)insertfor->left=nextinsertfor;
		else insertfor->right=nextinsertfor;
	}
	/*色の調整*/
	chouseicolor(nextinsertfor);
}

int search(node* root,int puttern) {
	node* current;
	current=root;
	while(current) {
		if(current->puttern==puttern)return current->kosuu;
		if(puttern<current->puttern)current=current->left;
		else current=current->right;
	}
	return -1;
}

void _freetree(node** taisyou) {
	if(*taisyou==NULL)return;
	_freetree(&((*taisyou)->left));
	_freetree(&((*taisyou)->right));
	free(*taisyou);
	*taisyou=NULL;
}

node* root[4][21][20]={NULL};

void freetree(void) {
	int k,y,x;
	for(k=0;k<4;k++) {
		for(y=0;y<21;y++) {
			for(x=0;x<21;x++)_freetree(&root[k][y][x]);
		}
	}
}

int countflags(char[21][21],int,int,int,int,int);

int main(int argc,char* argv[]) {
	char infile[255],outfile[255];
	FILE* in;
	FILE* out;
	/*declare values*/
	int tate,yoko;
	char map[21][21];
	int i;
	int x,y;
	int allflags;
	int badflags;
	int goodflags;
	/*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 %d",&tate,&yoko);
	for(i=1;i<=tate;i++)fscanf(in,"%s",map[i]);
	allflags=1;
	for(y=1;y<=tate;y++) {
		for(x=0;x<yoko;x++) {
			if(map[y][x]=='?')allflags=allflags*3%100000;
		}
	}
	strcpy(map[0],"IIIIIIIIIIIIIIIIIIII");
	badflags=countflags(map,0,1,0,yoko,tate+1);
	goodflags=allflags-badflags;
	if(goodflags<0)goodflags+=100000;
	fprintf(out,"%d\n",goodflags);
	/*file close*/
	fclose(in);
	fclose(out);
	return 0;
}

int countflags(char map[21][21],int x,int y,int maeputtern,int mx,int my) {
	int i;
	int nowputtern;
	int kosuu;
	int results;
	int nextx,nexty;
	nowputtern=maeputtern>>1;
	nowputtern&=~(((x>1?(map[y][x-1]=='O'):x>0?0:(map[y-1][mx-1]=='O'))?0:1)<<(mx-2));
	if(x>0 && map[y][x-1]=='J')nowputtern|=1<<(mx-1);
	kosuu=search(root[c2m(map[y][x])][y][x],nowputtern);
	if(kosuu>=0)return kosuu;
	results=0;
	if(x<mx-1) {
		nextx=x+1;
		nexty=y;
	} else {
		nextx=0;
		nexty=y+1;
	}
	if(nexty<my) {
		if(map[y][x]!='?') {
			if(map[y-1][x]=='J' && map[y-1][x+1]=='O' && map[y][x]=='I')results=0;
			else results=countflags(map,nextx,nexty,nowputtern,mx,my);
		} else {
			map[y][x]='J';
			results+=countflags(map,nextx,nexty,nowputtern,mx,my);
			map[y][x]='O';
			results+=countflags(map,nextx,nexty,nowputtern,mx,my);
			if(map[y-1][x]!='J' || map[y-1][x+1]!='O') {
				map[y][x]='I';
				results+=countflags(map,nextx,nexty,nowputtern,mx,my);
			}
			map[y][x]='?';
		}
	} else {
		switch(map[y][x]) {
			case 'J':
				results=1;
				break;
			case 'O':
				results=1;
				break;
			case 'I':
				if(map[y-1][x]!='J' || map[y-1][x+1]!='O')results=1;
				break;
			case '?':
				results=2;
				if(map[y-1][x]!='J' || map[y-1][x+1]!='O')results++;
				break;
		}
	}
	insert(&root[c2m(map[y][x])][y][x],nowputtern,results%100000);
	return results%100000;
}

[/tabs]

[たいちう]

赤黒木については試しに動かしてみようと思いましたが、
コンソールに現れる日本語が意味不明で使い方が判りません。
「個数」とは？「負でない個数」とは？

どのようなデータを入力したら、どのような出力がされるから、
赤黒木が正しく実装できたと言えるのか、良く考えながらテストしてください。
問題６に戻るのはその後にすべきでしょう。
（赤黒木に拘らないならば別ですが）

# 明日より数日書き込めないと思います。

[みけCAT]

赤黒木については試しに動かしてみようと思いましたが、
コンソールに現れる日本語が意味不明で使い方が判りません。
「個数」とは？「負でない個数」とは？

実際のプログラムで使うことを想定してテストコードを作ったのでこのような表現になりました。
「パターン」には、連想配列のキーとなる整数を入力してください。
「個数」には、そのキーに対するデータの整数を入力してください。
すでにあるキーを入力するとそのデータが表示されます。
「負でない」というのは、データがなかったことを示す-1と紛らわしくならないようにするためです。