Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/05/23

Google Code Jam 2010 Round 1B A. File Fix-it

| 07:16

http://code.google.com/codejam/contest/dashboard?c=635101#s=p0&a=0

問題

既に存在する UNIX 形式のディレクトリパスの集合がある時に,与えられたディレクトリパスのディレクトリを作る際に,いくつのディレクトリを作らなければならないかを求める問題.

結果

small, large 共に correct.

アプローチ

本番では問題の細かい条件までちゃんと読む時間がなかったので,要点だけ押さえて,思い付くまま多分木を作ってディレクトリ構造とディレクトリの作成をシミュレートした.

large でも特に問題が大きくないので set を使ってすべてのディレクトリパスを保存しても問題なさそう.

問題の条件を読み直したら

1 1
/home/yuyarin/test
/home/yuyarin

みたいなケースも無い,つまり既存のディレクトリパスについてはその上位のディレクトリのパス(/home/yuyarin,/home)も,既存ディレクトリパスの集合に含まれているので,作るかどうかは既存ディレクトリパスの集合にパスの文字列が有るか無いかだけで判定できる.

作るべきディレクトリに対しては上位ディレクトリを求めていって,それが集合に無ければ追加してカウントを増やせばいい.

ソースコード

初めから書き直したので,提出時とアルゴリズムが違う

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <set>

using namespace std;

typedef vector<string> VS;

#define Forall(i,v)   for(int i=0;i<(int)v.size();++i)
#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)
#define sz(a) int((a).size())

// using boost C++ library Version 1.41>=
// http://www.boost.org/
#include <boost/algorithm/string.hpp>

int main(int argc, char* argv[])
{
	int T;
	cin >> T;
	
	Rep(t,T)
	{
		int N, M;
		cin >> N >> M;
		VS ve(N);
		VS vc(M);
		set<string> sp;
		Rep(n,N)
		{
			cin >> ve[n];
			sp.insert(ve[n]);
		}
		int r = 0;
		Rep(m,M)
		{
			cin >> vc[m];
			VS vs;
			boost::algorithm::split(vs, vc[m], boost::is_any_of("/"));
			string s = "";
			For(i,1,sz(vs))
			{
				s = s + "/" + vs[i];
				if(sp.insert(s).second)
					r++;
			}
		}
		cout << "Case #" << t+1 << ": " << r << endl;
	}
	
	return 0;
}

AndiAndi2011/07/22 15:08Thanks alot - your answer solved all my problems after several days srtuglging

ymztwdpymztwdp2011/07/26 00:50iMKSlH , [url=http://vxqonjgohmzr.com/]vxqonjgohmzr[/url], [link=http://bdghiksyjeoz.com/]bdghiksyjeoz[/link], http://fqpjpgeffbmu.com/

EgwoloEgwolo2013/02/16 23:19Thanks for contributing. It's helepd me understand the issues.

zzokgazzokga2013/02/19 14:25gNeh7s <a href="http://jdxldqxslfbx.com/">jdxldqxslfbx</a>

ealpalshhtealpalshht2013/02/19 14:25ftpxVI <a href="http://cpdedlynamuf.com/">cpdedlynamuf</a>