Hatena::Grouptopcoder

hogloid @ TopCoder

 | 

2012-05-06

X Programming Olympiads in Murcia (Spain) 2012

17:05

なんかUvaでコンテストやってたので出てみた。

解けた問題で、わりとむずいかしいE,Gのみ


E. Oh, my trees! (UVa 12458)

二分探索木から辺が消えたものが与えられる。

すなわち、各頂点に割り当てられた数字とその高さがわかっている。

このとき、元の二分探索木を復元せよ。


G. Careful teacher (UVa 12460)

20000 文字以下からなる辞書が与えられる。

二つの文字列 s, t が与えられる。

s の一文字を変化させることを繰り返して t に一致させられるか判定せよ。

ただし、変化後の文字列は辞書に入っていないといけない。

(fura2さんの記事から拝借しました)


Eは、オーダーがよくわからないけど、

それぞれのレベルでキーの大きさでノードソートし、

あるノードの子孫に存在する可能性のある最も小さい値、最も大きい値

が分かっていれば、左の子はどれか、右の子はどれかが分かる。

これを再帰で表現すればおわり。根では最も小さい値を-INF,最も大きい値をINFにする

たぶんO(VlogV)

using namespace std;
static const int INF =INT_MAX-13;
typedef pair<int,int> pi;
int h;
vector<vector<int> > node;
char tmp[1000005];
stringstream ss;
int when;
map<int,int> conv;
int rev[1000005];
pi res[1000005];
void in(int lev){
	ss.clear();ss.str("");
	ss<<tmp;
	int a;
	while(ss>>a){
		rev[when]=a;
		conv[a]=when++;
		node[lev].push_back(a);
	}
};
void rec(int key,int lev,int lb,int ub){
	int nlb=lower_bound(node[lev+1].begin(),node[lev+1].end(),lb)-node[lev+1].begin(),
		nub=upper_bound(node[lev+1].begin(),node[lev+1].end(),ub)-node[lev+1].begin();
	if(nub-nlb==2){
		res[conv[key]]=make_pair(node[lev+1][nlb],node[lev+1][nlb+1]);
		rec(node[lev+1][nlb],lev+1,lb,key-1);
		rec(node[lev+1][nlb+1],lev+1,key+1,ub);
	}else if(nub-nlb==1){
		if(node[lev+1][nlb]<key){
			res[conv[key]]=make_pair(node[lev+1][nlb],INF);
			rec(node[lev+1][nlb],lev+1,lb,key-1);
		}else{
			res[conv[key]]=make_pair(INF,node[lev+1][nlb]);
			rec(node[lev+1][nlb],lev+1,key+1,ub);
		}
	}else{
		res[conv[key]]=make_pair(INF,INF);
	}
}
int main(){
	int t;scanf("%d",&t);
	while(t--){
		when=0;conv.clear();

		scanf("%d",&h);getchar();
		node.clear();node.resize(h+1);
		for(int i=0;i<h;++i){
			gets(tmp);
			in(i);
			sort(node[i].begin(),node[i].end());
		}
		rec(node[0][0],0,INT_MIN,INT_MAX);
		for(int i=0;i<when;++i){
			printf("%d:",rev[i]);
			if(res[i].first!=INF) printf("%d",res[i].first);
			putchar('-');
			if(res[i].second!=INF) printf("%d",res[i].second);
			putchar('\n');
		}
	}



	return 0;
}

Gも、文字列の長さとかクエリ数がよく分かんなくて困ったけど、

文字列の長さが辞書であるような常識的な長さと仮定すると、

文字列の長さでソートし、

それぞれの長さの文字列の集合について、

文字のk番目を無視して辞書順ソートする。

これで、文字のk番目を無視すると等しい文字列かどうかが高速に分かる。

k番目を無視したとき等しいなら、一文字しか違わなく、1文字変えてジャンプできるので、union-findか何かでマージする。

O(length^2 * N log N)ぐらい?

using namespace std;
static const int INF =500000000;
typedef long long int lint;
typedef pair<int,int> pi;
pair<string,int> strs[20005];
int deg[20005];
struct uf{
	int par[20005];
	uf(){
		memset(par,-1,sizeof(par));
	}
	int root(int a){
		if(par[a]==-1) return a;
		return par[a]=root(par[a]);
	}
	void unite(int a,int b){
		a=root(a);b=root(b);
		if(a==b) return;
		par[a]=b;
	}
	bool same(int a,int b){
		return root(a)==root(b);
	}
};
uf u;
bool cmp(const pair<string,int>& s,const pair<string,int>& s2){
	return s.first.size()<s2.first.size();
}
int except;
int compare(const string& s,const string& s2){
	for(int i=0;i<s.size();++i){
		if(i==except) continue;
		if(s[i]<s2[i]) return -1;
		if(s[i]>s2[i]) return 1;
	}
	return 0;
}
bool cmp2(const pair<string,int>& s,const pair<string,int>& s2){
	if(compare(s.first,s2.first)==-1) return true;
	return false;
}

int main(){
	string s;
	int n=0;
	while(getline(cin,s)){
		if(s=="--") break;
		strs[n]=make_pair(s,n);
		++n;
	}
	sort(strs,strs+n,cmp);
	for(int i=0;i<n;++i){
		int j=i,len=strs[i].first.size();
		while(j<n && strs[j].first.size()==len) ++j;
		if(j-i>1){
			for(int k=0;k<len;++k){
				except=k;
				sort(strs+i,strs+j,cmp2);
				for(int l=i;l<j;++l){
					int i2=l;
					while(i2<j && compare(strs[l].first,strs[i2].first)==0){
						u.unite(strs[l].second,strs[i2].second);
						++i2;
					}
					l=i2-1;
				}
			}
		}
		i=j-1;
	}
	sort(strs,strs+n);
	string a,b;
	stringstream ss;
	while(getline(cin,s)){
		int piv;
		ss.clear();ss.str("");
		ss<<s;
		ss>>a>>b;
		int A=lower_bound(strs,strs+n,make_pair(a,-1))->second,B=lower_bound(strs,strs+n,make_pair(b,-1))->second;
		if(u.same(A,B)) puts("Yes");
		else puts("No");
	}


	return 0;
}

trie木使えば、おそらくlog消える


結構面白い問題だったけど、やっぱり部分点ないのに最大ケース分からないというのはつらい

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/hogloid/20120506
 |