TopCoder SRM 823 : Div1 Hard Tigerrymander

800ptとはいえ、Hardの割にラク。
https://community.topcoder.com/stat?c=problem_statement&pm=17396

問題

合計N体の虎と牛がいる。
選挙を行ったとき、虎の数が牛の数のT/O倍より多いなら虎が代表となる。

ここで、虎は以下の工作ができる。

• 計n体の虎・牛がいるとき、それらを同じ数のグループに分ける。例えばm体のグループ(n/m)個に分ける。
• この時、各グループ内で選挙を行い、勝った側を代表としてグループ数分(n/m)体そろえ、その中でまた選挙してn体のうちの代表を決める。

虎は任意回数この操作を行うとき、代表を虎とするのに最小な数は何通りか。

解法

f(N) := 工作を行わない場合、計N体の虎・牛に対し、虎が代表となるのに必要な最小数
g(N) := 工作を行う場合、計N体の虎・牛に対し、虎が代表となるのに必要な最小数

f(N)はO(1)で計算できる。
あとは求めたいのはg(N)である。
あとはNの約数mに対し、g(N) = min(f(N/m)*g(m))を再帰的に求めればよい。

vector<ll> C;
map<ll,int> M;
ll dp[100000];
ll T,O;
class Tigerrymander {
	public:
	ll dfs(ll n) {
		if(dp[M[n]]>=0) return dp[M[n]];
		
		ll mi=(n*O+T+O)/(T+O);
		int i;
		FOR(i,C.size()) if(n%C[i]==0) {
			if(n==C[i]) break;
			ll w=dfs(C[i]);
			ll t=w*((n/C[i]*O+T+O)/(T+O));
			mi=min(mi,t);
			
		}
		
		return dp[M[n]]=mi;
		
	}
	
	long long minTigers(long long N, int TV, int OV) {
		C.clear();
		for(ll i=1;i*i<=N;i++) if(N%i==0) {
			C.push_back(i);
			if(i*i!=N) C.push_back(N/i);
		}
		sort(ALL(C));
		M.clear();
		int i;
		FOR(i,C.size()) M[C[i]]=i;
		T=TV,O=OV;
		
		MINUS(dp);
		return dfs(N);
		
	}
}

まとめ

計算時間を気にして定数倍高速化とかいろいろやったけど、あまり意味なかった様子。