Google code jam 2010 Round 1B A. File Fix-it

問題概要

Unixのディレクトリシステムにおいて、既に存在するディレクトリN個のリストと作りたいディレクトリM個のリストが与えられる。

新たにディレクトリを作りたい場合、その親ディレクトリがなければ親ディレクトリも作成する必要がある。（更にその親ディレクトリもなければ、親の親を作る必要がある……と再帰的に繰り返す）

このとき、必要なディレクトリ作成の回数を求めよ。
ただし、ルートディレクトリ"/"は最初から存在するものとする。
0≦M,N≦100である。

解法

N,Mが小さいので別に効率化を考える必要はない。
既に存在するディレクトリのパスをsetで持っておいて、新たに作りたいディレクトリの親がないときはパスを後ろから"/"一個ずつ消して、存在するディレクトリを探し（&生成し）ていけばよい。

ソースコード

int main()
{
	int CS; cin>>CS;
	rep(cs,CS)
	{
		int n,m; cin>>n>>m;
		set<string> S; S.insert("/"); S.insert("");
		
		int ans=0;
		string str;
		rep(i,n)
		{
			cin>>str;
			S.insert(str);
		}
		rep(i,m)
		{
			cin>>str;
			int make=0;
			while(!S.count(str))
			{
				S.insert(str);
				
				int p=str.rfind("/");
				str=str.substr(0,p);
				make++;
			}
			ans+=make;
		}
		
		cout<<"Case #"<<cs+1<<": "<<ans<<endl;
	}
	
	return 0;
}