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>

2010/03/20

SRM 464 ColorfulStrings

| 21:19

http://www.topcoder.com/stat?c=problem_statement&pm=10724&rd=14149

Sample Case: passed

System Test: passed

問題の条件から

  • 2桁以上の数字では0と1が入ってはいけない
  • 同じ数字は2回現れない

ということがわかるので 2<=n<=8 で考えればいいことがわかるので,ひとまず枝刈りをせずに 2,3,4,5,6,7,8,9 を辞書順で生成していき colorful かチェックする.結果的に枝刈りをしなくても実行速度は十分であった.

数字は整数の配列 num[] で各桁を表現する.

辞書順の生成は再帰を使う (rec()).ある数字が使われたかを ap[] で記録しておき,使われていない数字を小さい方から num[pos] に入れていく.pos を 1 増やして再帰する.長さが桁数に達したら colorful かチェックを行う (colorful()).

colorful のチェックではそれまでの数字の積を記録 (mr[]) しておけば,ループを1重減らすことができる.

積のデータベースには set を利用している.insert() は既に要素があったときに .second で false が返されるので,既に積が出現している=colorful ではない場合を挿入と同時に判定できる.

あんまりスマートなコードだとは思わないけど,理解はしやすいと思う.

上位のコードはもっとシンプルだけどまだ解読出来ていない...

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

using namespace std;
inline int toi(string s){int v; istringstream iss(s);iss>>v;return v;}
template<class T> inline string tos(T x){ostringstream oss;oss<<x;return oss.str();}

class ColorfulStrings
{
public:

bool colorful(int n, int* num)
{
	// the results of mul
	int mr[] = {1,1,1,1,1,1,1,1,1,1,};
	
	set<int> m;
	
	for(int len=1; len<=n; ++len)
	{
		for(int idx=0; idx<=n-len; ++idx)
		{
			mr[idx] *= num[idx+len-1];
			if(!m.insert(mr[idx]).second)
				return false;
		}
	}
	
	return true;
}

bool rec(int n, int k, int* num, int* ap, int pos, int &cnt)
{
	if(pos==n)
	{
		if(colorful(n, num)) cnt++;
		if(cnt==k) return true;
		return false;
	}
	
	for(int i=2; i<10; ++i)
	{
		if(ap[i]) continue;
		num[pos] = i;
		ap[i] = 1;
		if(rec(n, k, num, ap, pos+1, cnt)) return true;
		ap[i] = 0;
	}
	return false;
}

string getKth(int n, int k)
{
	if(n>8) return "";
	if(n==1) return (k>10) ? "" : tos(k-1);
	
	string s = "";
	int num[8];
	int ap[] = {0,0,0,0,0,0,0,0,0,0};
	int cnt = 0;
	
	if(rec(n, k, num, ap, 0, cnt))
	{
		for(int i=0; i<n; ++i) s += num[i]+'0';
	}
	return s;
}
	
	
};

ElenaElena2013/02/17 05:39That addresses several of my concerns acutlaly.

sdxtpjsdxtpj2013/02/18 07:467hgOED , [url=http://vkhpudkqbafn.com/]vkhpudkqbafn[/url], [link=http://ibikxlgbdgkx.com/]ibikxlgbdgkx[/link], http://trdttgtbmydr.com/

beidpbknybeidpbkny2013/02/19 14:45wqJCeV <a href="http://pkzbvtmxkrzw.com/">pkzbvtmxkrzw</a>

hcaepwobinzhcaepwobinz2013/02/19 20:07MApC6d , [url=http://desrxojmthft.com/]desrxojmthft[/url], [link=http://qcvljhvzomoh.com/]qcvljhvzomoh[/link], http://socvhhjtbmkl.com/