kmjp's blog

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

Google Code Jam 2013 Qualification Round : C. Fair and Square

GCJ

さてここからが本番。
GCJとしては珍しくLargeが２段階ある。
https://code.google.com/codejam/contest/2270488/dashboard#s=p2

問題

ある数がFair and Squareであるというのは、その数字が回文である上に、回文の二乗になっていることである。
２つの数A,Bが与えられたとき、A<=X<=Bに当てはまるFair and Squareな数Xの数を答えよ。

解法(Small～Large1)

このA<=X<=Bに当てはまる数を答える問題、GCJに多いね。
これば0～Bに当てはまる数から、0～(A-1)に当てはまる数を引けばよい。

0～Bに当てはまるはずだけど、Bは高々10^14。
よって10^7までの数の二乗になっているはず。
高々10^7ならループを回しても間に合うので、先に10^7までの数のうち回文になるものを二乗し、その値も回文になるものをFair and Squareな数を列挙してしまえばよい。
ちなみに最大の10^14までのうちFair and Squareなものは39個しかない。

Fair and Squareな数を列挙できたら、後はB以下の数を数えればよい。

vector<ll> list;

int parp(char* str) {
	int i,l;
	l=strlen(str);
	FOR(i,l) if(str[i]!=str[l-1-i]) return 0;
	return 1;
}

int parp(ll n) {
	char h[200];
	sprintf(h,"%lld",n);
	return parp(h);
}

int num(ll L) {
	int i;
	while(i<list.size()-1 && L>=list[i]) i++;
	return i;
}

ll A,B;

void solve(int _loop) {
	
	scanf("%lld %lld",&A,&B);
	_PE("Case #%d: %d\n",_loop,num(B)-num(A-1));
}

void init() {
	ll i;
	FOR(i,10000003) {
		if((i/100)%10>=3) {i+=99; continue;}
		if((i/10)%10>=3) {i+=9; continue;}
		if(i%10>=4) continue;
		if(parp(i) && parp(i*i)) list.push_back(i*i);
	}
}

解法(Large2)

こちらは桁数が10^100まで増えるので、10^50までの回文を二乗する…のは計算量的に無理。
試しに先の10^14までのケースを見ると、以下の法則がわかる。

  1. 回文を二乗する場合、各桁で繰り上がりが発生してはならない
  2. Fair and Squareな数では、最大値は真ん中の桁にくる

よって、真ん中の桁が９以下になるようにすればよい。
２乗しても真ん中の桁が９以下になる数値は以下のパターンである。
これらに対して２乗した値がFair and Squareな数になる。

  • 1桁の場合
    • 1か4か9のみ
  • 3ケタ以上の奇数桁の場合
    • 真ん中が2の場合
      • 両端の桁は1のみ。先頭と真ん中の間に、1があと0～1個入り、あとは0。
    • 真ん中の桁は0か1の場合
      • 両端の桁が2の場合、真ん中と先頭の桁の間は0のみ。
      • 両端の桁が1の場合、先頭と真ん中の間に、1があと0～3個入り、あとは0。
  • 偶数桁の場合
    • 両端の桁が2の場合、真ん中と先頭の桁の間は0のみ。
    • 両端の桁が1の場合、先頭と真ん中の間に、1があと0～3個入り、あとは0。

これらの数は10^50までに41548個しかない。
あとはSmall～Large1同様数を数えるだけ。

一応先の２法則は証明できそうだ。
１つ目はあるところで桁上がりが発生すると、そこと対象の位置で逆方向の桁上がり？が発生しないと回文にならないので、途中で桁上がりは発生できない。
２つ目は、例えば２つの桁の値xとyがあったとき、真ん中の桁はx^2+y^2が加算されるが、別の桁は2xyが加算される。相加相乗平均の法則より、前者の方が大きい。

vector<ll> list;
int C[102][102];
vector<string> str[201];

int parp(char* str) {
	int i,l;
	l=strlen(str);
	if(l==1) return (str[0]=='1' ||str[0]=='4' || str[0]=='9');
	FOR(i,l) if(str[i]!=str[l-1-i]) return 0;
	return 1;
}

void enums(int keta) {
	char s[300];
	int i,x,y,z,l;
	ZERO(s);
	FOR(i,keta) s[i]='0';
	
	if(keta%2==1) {
		// top=2
		s[0]=s[keta-1]='2';
		str[keta*2-1].push_back(s);
		s[(keta-1)/2]='1';
		str[keta*2-1].push_back(s);
		
		// top=1 mid=2
		s[0]=s[keta-1]='1';
		s[(keta-1)/2]='2';
		str[keta*2-1].push_back(s);
		for(i=1;i<keta/2;i++) {
			s[i]=s[keta-1-i]='1';
			str[keta*2-1].push_back(s);
			s[i]=s[keta-1-i]='0';
		}
		
		FOR(l,2) {
			s[(keta-1)/2]='0'+l;
			
			str[keta*2-1].push_back(s);
			for(x=1;x<keta/2;x++) {
				s[x]=s[keta-1-x]='1';
				str[keta*2-1].push_back(s);
				for(y=x+1;y<keta/2;y++) {
					s[y]=s[keta-1-y]='1';
					str[keta*2-1].push_back(s);
					for(z=y+1;z<keta/2;z++) {
						s[z]=s[keta-1-z]='1';
						str[keta*2-1].push_back(s);
						s[z]=s[keta-1-z]='0';
					}
					s[y]=s[keta-1-y]='0';
				}
				s[x]=s[keta-1-x]='0';
			}
		}
	}
	else {
		// top=2 mid=0
		s[0]=s[keta-1]='2';
		str[keta*2-1].push_back(s);
		
		// top=1 mid=2
		s[0]=s[keta-1]='1';
		str[keta*2-1].push_back(s);
		for(x=1;x<keta/2;x++) {
			s[x]=s[keta-1-x]='1';
			str[keta*2-1].push_back(s);
			for(y=x+1;y<keta/2;y++) {
				s[y]=s[keta-1-y]='1';
				str[keta*2-1].push_back(s);
				for(z=y+1;z<keta/2;z++) {
					s[z]=s[keta-1-z]='1';
					str[keta*2-1].push_back(s);
					s[z]=s[keta-1-z]='0';
				}
				s[y]=s[keta-1-y]='0';
			}
			s[x]=s[keta-1-x]='0';
		}
	}
	
	// square
	s[keta*2-1]=0;
	FOR(i,str[keta*2-1].size()) {
		FOR(x,keta*2-1) s[x]='0';
		FOR(x,keta) {
			if(str[keta*2-1][i][x]!='0') FOR(y,keta) s[(keta*2-2)-(x+y)]+=(str[keta*2-1][i][keta-1-x]-'0')*(str[keta*2-1][i][keta-1-y]-'0');
		}
		str[keta*2-1][i]=s;
	}
	
	sort(str[keta*2-1].begin(),str[keta*2-1].end());
}

int enumk(int keta) {
	int num;
	if(keta==1) return 3;
	if(keta%2==1) {
		num = 2; // top=2,mid=0,1
		// top=1,mid=0,1,left=0,1,2,3
		num += 2*(C[(keta-3)/2][0]+C[(keta-3)/2][1]+C[(keta-3)/2][2]+C[(keta-3)/2][3]);
		// top=1,mid=2,left=0,1
		num += (C[(keta-3)/2][0]+C[(keta-3)/2][1]);
	}
	else {
		num = 1; // top=2, mid=0
		// top=1,left=0,1,2,3
		num += C[(keta-2)/2][0]+C[(keta-2)/2][1]+C[(keta-2)/2][2]+C[(keta-2)/2][3];
	}
	return num;
	
}

int num(char *st, int inc) {
	int l=strlen(st);
	int n=0,i;
	
	FOR(i,l) n+=str[i].size();
	FOR(i,str[l].size()) {
		if((inc && str[l][i]>st) || (!inc && str[l][i]>=st)) break;
		n++;
	}
	return n;
}


ll A,B;

void solve(int _loop) {
	char A[200];
	char B[200];
	
	GETs(A);
	GETs(B);
	_PE("Case #%d: %d\n",_loop,num(B,1)-num(A,0));
}

void init() {
	ll i;
	int x,y;
	ZERO(C);
	FOR(x,101) C[x][0]=C[x][x]=1;
	for(x=1;x<=100;x++) for(y=1;y<x;y++) C[x][y]=C[x-1][y-1]+C[x-1][y];
	
	str[1].push_back("1");
	str[1].push_back("4");
	str[1].push_back("9");
	
	for(x=2;x<=50;x++) enums(x);
}

まとめ

Large2まできちっと解き切れてよかった。
面白い問題だったね。