kmjp's blog

競技プログラミング参加記です

TopCoder SRM 843 : Div1 Medium TallyMarksSystem

うーむ。
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多かったね。