うーむ。
https://community.topcoder.com/stat?c=problem_statement&pm=17955
問題
正整数Nが与えらえる。
1,5,+,*,括弧だけを使い、Nとなる式を構築したい。
登場する数字の数は最小いくつか。
解法
f(n) := nと評価される式における数字の数の最小値
とすると、まず以下が成り立つ。
- f(0) = 0
- f(1) = f(5) = 1
- f(a*b) ≦ f(a) + f(b)
- f(a+b) ≦ f(a) + f(b)
3つ目までの条件であれば、O(NlogN)でf(0)~f(N)まで列挙できるが、4つ目の条件を愚直に処理するとO(N^2)かかる。
実験すると、4つ目の条件でf(n)が最小となるケースでは、aまたはbが取る値はかなり限定されており、かつ3000以下である。
よってその範囲のみ4つ目の条件をチェックすればよい。
とはいえN*3000回ループするとTLEするので、値をもう少し限定しよう。
int dp[2020202]; vector<int> SP={1008,1057,1086,1092,1134,1250,1524,1661,1716,1757,1764,1806,1827,1836,2265,2871}; class TallyMarksSystem { public: int construct(int N) { int i; FOR(i,2010101) dp[i]=30; dp[0]=0; int j; for(i=1;i<=N;i++) { dp[i]=min(dp[i-1]+1,dp[i]); if(i>=5) dp[i]=min(dp[i],dp[i-5]+1); for(j=1;j<=min(i-1,1000);j++) dp[i]=min(dp[i],dp[j]+dp[i-j]); FORR(j,SP) if(j<i) dp[i]=min(dp[i],dp[j]+dp[i-j]); for(j=2;j*i<=2010101&&j<=i;j++) dp[i*j]=min(dp[i*j],dp[i]+dp[j]); } return dp[N]; } }
まとめ
今回EasyもMediumもChallenge多かったね。