Autumn Fest 2012 : G Bit Map

さて続いて７問目。
http://autumn_fest.contest.atcoder.jp/tasks/autumn_fest_07

この問題、終了後に解いたら意外と簡単に解けた。
関数定義が面倒で面食らうけど、これ実装ゲーだな…。

まず、関数定義のパーサーは頑張って書くしかない。
数値以外は１文字だし、先読みが必要な変な文法もないので丁寧に処理して以降。

この問題の関数定義は、and・or・xorしか使わないので、異なるビット位置同士は影響しない。
よって、各ビット入力が0と1の時の結果を考えればよい。
さらに言えば、関数FについてはF(0)とF(0x7FFFFFFF)の２つだけ計算すれば各ビットの出力がわかる。

結局、入力値xに対して、各出力ビットの取りうるケースは以下のいずれか

0→0、1→0 : xにかかわらず0
0→1、1→1 : xにかかわらず1
0→0、1→1 : xと同じ
0→1、1→0 : xと逆

この問題では、F^1234(x)といったように関数の合成が可能だが、上の通り出力ケース1,2,3は複数回繰り返しても結果が同じで、ケース4は偶数・奇数で結果が異なるだけ。
よって、合成回数が多くても、3回以上の合成は結局２回以下の合成と同じ結果が得られるので、実際に何度も合成する必要はない。

さて、各関数の出力ビットパターンがわかったところで、それを50文字以下で表現しなおさないといけない。
各ビットについて、先の４パターンのビットごとに和集合をとる。

A : xにかかわらず0になるビットの和集合
B : xにかかわらず1になるビットの和集合
C : xと同じ値を返すビットの和集合
D : xと逆の値を返すビットの和集合

こうすると関数F(x)の短縮表現は $F(x)=(B|( (x&(C|D) )\^D) )$ となる。
このままだと、B,C,Dは最大９ケタなので合計で50文字を溢れてしまうが、(C|D)は先に計算した値を置くことで、９ケタの数値は最大３か所にしか現れず、50文字に収めることができる。

int N;
int func[26][2];
char str[2000];

int dofunc(char funcname, int cv,int loop) {
	int v,nv,id,nl;
	nl=loop;
	if(nl>2) nl=nl%2+2;
	
	v=cv;id=funcname-'a';
	while(nl--) {
		v = (func[id][0] & (~v)) |(func[id][1] & (v));
	}
	//_P("%c %d->%d(%d)\n",funcname,cv,v,loop);
	return v;
}

pair<int,char*> val(char* pc, int cv) {
	pair<int,char*> p;
	char fn;
	int v,loop,lh,rh;
	//_P("%s\n",pc);
	
	if(*pc=='x') return make_pair(cv,pc+1);
	if(*pc>='0' && *pc<='9') {
		v=0;
		while(*pc>='0' && *pc<='9') {
			v=v*10+(*pc-'0');
			pc++;
		}
		return make_pair(v,pc);
	}
	if(*pc>='a' && *pc<='j') {
		fn=*pc;
		pc++;
		loop=1;
		if(*pc=='^') {
			pc++;
			loop=0;
			while(*pc>='0' && *pc<='9') {
				loop=loop*10+(*pc-'0');
				pc++;
			}
		}
		pc++; // (
		p = val(pc,cv);
		pc=p.second+1; // )
		return make_pair(dofunc(fn,p.first,loop),pc);
	}
	if(*pc=='('){
		p = val(pc+1,cv);
		lh=p.first;
		pc=p.second;
		fn=*pc;
		
		p = val(pc+1,cv);
		rh=p.first;
		if(*pc=='|') return make_pair(lh|rh,p.second+1);
		if(*pc=='^') return make_pair(lh^rh,p.second+1);
		if(*pc=='&') return make_pair(lh&rh,p.second+1);
		_P("error op %s\n",pc);
	}
	
	_P("error %s\n",pc);
	
	return make_pair(0,pc);
}

まとめ

見た目複雑だけど、意外と単純な問題。
パーサーを自前で書くのは面倒だけど、慣れといた方が良さそうだ。
JavaだとTokernizerあるけど、Cにはないよね…。

kmjp's blog

競技プログラミング参加記です

Autumn Fest 2012 : G Bit Map

まとめ