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); } }
まとめ
計算時間を気にして定数倍高速化とかいろいろやったけど、あまり意味なかった様子。