TopCoder SRM 722 Div1 Easy TCPhoneHome、Div2 Medium TCPhoneHomeEasy

Mediumでグダってレート微減。むしろ微減で済んでよかったというか。
https://community.topcoder.com/stat?c=problem_statement&pm=14698
https://community.topcoder.com/stat?c=problem_statement&pm=14728

問題

Leading zeroをゆるし、D桁の整数を考える。
prefixが文字列集合Sに含まれないものは何通りか。

解法

S[i]のprefixがS[j]である場合、D桁の整数中S[j]がprefixなものを取り除けば、S[i]となるものも取り除かれるのでS[i]は無視してよい。

よって10^D個の要素から、無視できないS[j]について10^(D-|S[j]|)を引けばよい。

class TCPhoneHome {
	public:
	long long validNumbers(int digits, vector <string> S) {
		int N=S.size();
		int invalid[100]={};
		ll p10[20];
		int i,j;
		p10[0]=1;
		FOR(i,18) p10[i+1]=p10[i]*10;
		
		ll ret=p10[digits];
		FOR(i,N) {
			FOR(j,N) if(i!=j) {
				if(S[j].size()<S[i].size() && S[i].substr(0,S[j].size())==S[j]) invalid[i]=1;
			}
			if(invalid[i]==0) {
				ret-=p10[digits-S[i].size()];
			}
		}
		return ret;
		
	}
}

まとめ

D桁以下とかにすればもう少しちょうどいい難易度だったかも。