TopCoderOpen 2019 Round2B : Medium DivisorSequences

なんか「あれ、先日のCodeforcesに近い？」と思っちゃった。
https://community.topcoder.com/stat?c=problem_statement&pm=15526

問題

正整数Nが与えられる。
以下を満たす最長の正整数列A[i]の長さを求めよ。

• sum(A) = N
• A[i+1]はA[i]より大きなA[i]の倍数である

解法

f(x) := sum(A)=xで、A[i+1]がA[i]より大きなA[i]の倍数であるような数列Aのうち、先頭要素が2以上であるものの最長の長さ
とする。
初手を1にするかそれ以外にするか、を考えると、求める値はmax(f(N), f(N-1)+1)である。

あとはf(x)を考えよう。
先頭要素をyとすると、数列の全要素はyの倍数でなければならない。
よってxの約数のうち1以外であるyを総当たりし、
f(x) := max(1+f(x/y-1))
を再帰的に求めればよい。

map<int,int> M;

class DivisorSequences {
	public:
	
	int longest(int N) {
		if(N==0) return 0;
		if(N<=2) return 1;
		if(M.count(N)) return M[N];
		
		int i,j;
		int ma=2;
		for(i=1;i*i<=N;i++) if(N%i==0) {
			vector<int> C={i,N/i};
			
			FORR(c,C) {
				int le=(N-c)/c;
				for(j=2;j*j<=le;j++) if(le%j==0) {
					ma=max(ma,1+longest(le/j));
					ma=max(ma,1+longest(j));
				}
			}
		}
		return M[N]=ma;
	}
}

まとめ

計算量ちょっと心配だったけど、通ってよかった。