Google Code Jam 2021 Round 2 : B. Matrygons

ちょっと手間取ったけど、無事解けた。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000435915/00000000007dbf06

問題

正A角形の中に、頂点を共有する正B角形(BはAの約数)があり、さらにそれがネストしているような図形を考える。
ここで整数Nが与えられる。辺の総数がNのもののうち、ネストが一番深いのはいくつか。

解法

以下の数値をDFSなどで前もって計算しておく。
f(x) := 辺の総数が一番内側の図形のx倍であるような図形のうち最大のネスト数
Nの上限は10^6で、一番内側の図形は三角形なので、xは10^6/3まで計算すればよい。

あとは、Nに対してはNのうち3以上約数dにおいてf(d)の最大値を答える。

int B[1010101];
int N;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	int ma=0;
	for(x=1;x*x<=N;x++) if(N%x==0) {
		if(x>=3) ma=max(ma,B[N/x]);
		y=N/x;
		if(y>=3) ma=max(ma,B[N/y]);
		
	}
	_P("Case #%d: %d\n",_loop,ma);
}

void dfs(int cur,int sum, int num) {
	if(sum>1000000/3+5) return;
	B[sum]=max(B[sum],num);
	
	int i;
	for(i=cur*2;sum+i<=1000000/3+5;i+=cur) {
		dfs(i,sum+i,num+1);
	}
	
}

void init() {
	int i,j;
	
	dfs(1,1,1);
}

まとめ

f(x)をx=1000000まで計算したら20秒超えたのでちょっと焦った。