Codeforces 65 D. Harry Potter and the Sorting Hat

Codeforces 探索

問題

人に次のようなルールで所属するファミリーを決める。
ファミリーは4つある。

  • あらかじめ決められたファミリーがある人は、そのファミリーに所属する。
  • そうでない人は、今までに割り振られた人数が最も少ないファミリー（複数ある場合好きなものを選べる）に所属する。


自分の前にn人の所属するファミリーを決める。
n人があらかじめ決められた割り当てがあるかどうかは文字列として与えられる。


自分にあらかじめ決められたファミリーはない。
自分が所属できる可能性のあるファミリーを全て出力せよ。

制約条件

n≦10000
ファミリーの数は4つ

方針

メモ化+全探索。


あらかじめファミリーを決められていない人は、
「今までに割り当てられた人数が最も少ないファミリー」に所属することになるので、
実際の状態数はかなり少なくなるので、nがそこそこ大きいが全探索で間に合う。

ソースコード

int n;
string in;
set<vector<int> > S;

void run()
{
	vi v(4);
	cin>>n>>in;
	queue<vi> q1,q2;
	queue<vi> *cur=&q1,*next=&q2;
	
	cur->push(v);
	rep(i,n){
		*next=queue<vi>();
		while(!cur->empty()){
			v=cur->front(); cur->pop();
			if(in[i]=='G'){
				v[0]++;
				if(!S.count(v))next->push(v), S.insert(v);
			}
			else if(in[i]=='H'){
				v[1]++;
				if(!S.count(v))next->push(v), S.insert(v);
			}
			else if(in[i]=='R'){
				v[2]++;
				if(!S.count(v))next->push(v), S.insert(v);
			}
			else if(in[i]=='S'){
				v[3]++;
				if(!S.count(v))next->push(v), S.insert(v);
			}
			else{
				int mn=*min_element(all(v));
				rep(i,4)if(v[i]==mn){
					v[i]++;
					if(!S.count(v))next->push(v), S.insert(v);
					v[i]--;
				}
			}
		}
		swap(cur,next);
	}
	
	bool ok[4]={};
	while(!cur->empty()){
		v=cur->front(); cur->pop();
		int mn=*min_element(all(v));
		rep(i,4)if(mn==v[i])ok[i]=1;
	}
	const char *name[]={"Gryffindor", "Hufflepuff", "Ravenclaw", "Slytherin"};
	rep(i,4)if(ok[i])cout<<name[i]<<endl;
}