Google Code Jam 2008 Round 1C : B. Ugly Numbers

さて２問目。流石に１問目よりは難しい。
http://code.google.com/codejam/contest/32015/dashboard#s=p1

数字の文字列が与えられたときに、間に+-を挟んでUgly Numberになる組み合わせ数を求める。
2か3か5か7で割り切れるとUglyである。

最近はこういう問題を見るとすぐDPだなと考えられるようになってきた。
2,3,5,7の最小公倍数は210なので、途中経過を余りが0～219になるパターンの数を数えていこう。

下の位からDPしていくとして、対象の数をXXXXYZZZZWWWWと分解して考えてみる。Yが今注目しているケタ(コード中のx)。
上の桁Xは無視し、YZZZZがくっついて一連の数字になると考える。WWWWは間に+-が入っていても構わない。

ここで、まずWWWWの余りが0～219になるパターン数はDPですでに計算済みのはず。
ここから、YZZZZ+(WWWW)とYZZZZ-(WWWW)の余りが求まるので、その数を累積していく。
各YごとにZやWの長さは変わる(コード中のy)。
最後に、余りが2,3,5,7で割り切れるものを累積していけばよい。

状態数はYの位置とZの数がN通り、あと210通りの余り毎に計算するので、O(210*N^2)だね。

const s64 mm=2*3*5*7;
int L;
int MOD[50][50];
char str[100];
s64 dp[50][50][mm];
s64 dp2[50][mm];

int calcmod(int s,int e) {
	char st[100];
	s64 v;
	int iv=0,i;
	int t=1;
	
	strcpy(st,&str[s]);
	st[e-s]=0;
	sscanf(st,"%lld",&v);
	
	for(i=e-s-1;i>=0;i--) {
		iv += t*(st[i]-'0');
		t = (t*10)%mm;
	}
	iv%=mm;
	
	
	
	//_P("%d %d %s %lld %d\n",s,e,st,v,iv);
	return iv;
	
	
}

void solve(int _loop) {
	int i,j,k,l,x,y;
	s64 res = 0;
	
	GETs(str);
	L=strlen(str);
	ZERO(MOD);
	FOR(i,L) {
		for(j=i+1;j<=L;j++) MOD[i][j]=calcmod(i,j);
	}
	
	if(L==1) {
		int v=MOD[0][1];
		_PE("Case #%d: %d\n",_loop,(v==1)?0:1);
		return;
	}
	
	ZERO(dp);
	ZERO(dp2);
	for(x=L-1;x>=0;x--) {
		dp[x][L][MOD[x][L]]+=1;
		if(x>0) dp[x][L][(mm-MOD[x][L])%mm]+=1;
		
		for(y=L-1;y>=x+1;y--) {
			int m = MOD[x][y];
			
			FOR(i,mm) {
				dp[x][y][(m+i)%mm]+=dp2[y][i];
				if(x>0) dp[x][y][(mm-m+i)%mm]+=dp2[y][i];
			}
		}
		for(y=L;y>=x+1;y--) {
			FOR(i,mm) dp2[x][i]+=dp[x][y][i];
		}
	}
	
	res=0;
	FOR(i,mm) if((i%2==0)||(i%3==0)||(i%5==0)||(i%7==0)) res+=dp2[0][i];
	
	_PE("Case #%d: %lld\n",_loop,res);
}

まとめ

このクラスの問題がノーヒントで解けるようになってきたのはいい傾向だ。
DPが苦手だったけど少し改善されてきたかな。
SRM 557 Div2 Hard FoxAndMountainとか、SRM 556 Div1 : Medium LeftRightDigitsGame2とかも似てるね。