TopCoder SRM 842 : Div1 Easy Div2 Hard StringReduction

ベストではないが悪くない出来。
https://community.topcoder.com/stat?c=problem_statement&pm=17920

問題

文字列Sと、ルールが与えられる。
ルールは、ある文字YがX個連続しているとき、1つ残して消すことができるというものである。

Sを任意にソートできるとき、ルールに従うとSは最小何文字にできるか。

解法

結局文字種ごとに文字数を数え、ルールに従いどこまで減らせるか数えるだけ。
後者は単純なDPである。

class StringReduction {
	public:
	int hoge(int S,vector<int> D) {
		int dp[2525]={};
		dp[S]=1;
		
		int mi=S;
		int i;
		for(i=2520;i>=0;i--) if(dp[i]) {
			mi=min(mi,i);
			FORR(d,D) if(d<=i) dp[i-d]=1;
		}
		return mi;
	}
	int reduce(string start, vector <int> X, string Y) {
		int C[26]={};
		vector<int> D[26];
		int i;
		FOR(i,Y.size()) {
			D[Y[i]-'a'].push_back(X[i]-1);
		}
		FORR(c,start) C[c-'a']++;
		
		int ret=0;
		FOR(i,26) if(C[i]) ret+=1+hoge(C[i]-1,D[i]);
		return ret;
	}
}

まとめ

この問題よく意図がわからなかったな…。