CSAcademy Round #30 : D. Prefix Free Subset

解いた時間は最速だったのに、つまらないミスで順位を落とした。
https://csacademy.com/contest/round-30/task/prefix-free-subset/

問題

N個の文字列のうちK個を選ぶ。
その時、選んだうちのある文字列sが他の文字列tのprefixになるということがないようにしたい。
そのような選び方のうち、最長の文字列の長さの最小値を求めよ。

解法

求める解をXとする。

文字列sがtのprefixだったとする。
この時、sを選んだ方がいいのは、|s|≦X＜|t|の場合のみであり、|t|≦Xならtを選んだ方が良い。
なぜなら、他の文字列Uに対し、sがUのprefixとなるよりtがUのprefixとなる可能性の方が低いためである。

まず全文字列をソートしよう。
各文字列tに対し、末尾を1文字ずつ削り、他の文字列sと一致したとする。
その時、上記のとおりsは|s|≦X＜|t|の場合に採用することになる。

よってimos法の要領で|s|≦X＜|t|であるXに対し(sを採用するので)解に1加算するということを計算しよう。
sに対しtの候補は複数ある場合があるが、その場合最短のtの影響を受けることとすればよい。

int K,N;
string S[1010101];
map<string,int> M;
int tar[1010101];
int ma[1010101];
int dif[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>S[i];
	sort(S,S+N);
	
	FOR(i,N) {
		ma[i]=1010101;
		s=S[i];
		
		while(s.size()) {
			if(M.count(s)) {
				tar[i]=M[s];
				ma[tar[i]]=min(ma[tar[i]],(int)S[i].size());
				break;
			}
			s.pop_back();
		}
		M[S[i]]=i;
	}
	FOR(i,N) {
		dif[S[i].size()]++;
		dif[ma[i]]--;
	}
	
	int ret=0;
	for(i=1;i<=1000002;i++) {
		dif[i]+=dif[i-1];
		if(dif[i]>=K) return _P("%d\n",i);
	}
	_P("-1\n");
	
}

まとめ

TLE怖かったけど割とすんなり。