kmjp's blog

競技プログラミング参加記です

Google Code Jam 2013 Qualification Round : D. Treasure

GCJ

さてD。本番はSmallが精一杯で、Largeは解説を見てトライ。
https://code.google.com/codejam/contest/2270488/dashboard#s=p3&a=3

問題

いくつかの宝箱と、鍵がある。
各宝箱は、対応する鍵を１つ消費して開けることができる。
宝箱の中には、いくつかの鍵が入っている。

宝箱を開ける鍵と、宝箱の中身と、最初に持っている鍵が与えられたとき、全部の箱を開けられるか答える。開けられる場合、辞書順で一番早い順番は答える。

解法(small)

宝箱は最大20個なので、BitDPで2^20通りの状態から、次に開けられる箱を列挙していけばよい。

string res,ma;
int N,K;
vector<int> FK;
int NK[201];
vector<int> key[201];

int sta[201];
map<int,int> memo;


int dfs(int mask) {
	int i,j,x,y,d;
	int kk[201];
	ZERO(kk);
	
	if(memo.find(mask)!=memo.end()) return memo[mask];
	if(mask==(1<<N)-1) {
		FOR(i,N) {
			_PE(" %d",sta[i]);
		}
		_PE("\n");
		return 1;
	}
	
	FOR(i,K) kk[FK[i]]++;
	d=0;
	FOR(i,N) if(mask & (1<<i)) {
		d++;
		kk[NK[i]]--;
		FOR(j,key[i].size()) kk[key[i][j]]++;
	}
	
	FOR(i,N) if(!(mask & (1<<i)) && kk[NK[i]]>0) {
		sta[d]=i+1;
		if(dfs(mask | (1<<i))==1) return memo[mask]=1;
	}
	
	return memo[mask]=0;
}

void solve(int _loop) {
	int i,x,y;
	
	GET2(&K,&N);
	FK.clear();
	FOR(i,K) FK.push_back(GETi()-1);
	char s[300];
	ZERO(s);
	FOR(i,N) {
		s[i]=255;
		NK[i]=GETi()-1;
		key[i].clear();
		y=GETi();
		FOR(x,y) key[i].push_back(GETi()-1);
	}
	
	memo.clear();
	ZERO(sta);
	_PE("Case #%d:",_loop);
	if(dfs(0)==0) {
		_PE(" IMPOSSIBLE\n",_loop);
	}
}

解法(Large)

解説によると、全部を開けられるかどうかは以下と同値である。

  • 宝箱の中身を含めた全部の鍵の数が、全宝箱を開けられる分に足りている
  • 「ある鍵を１つでも持っている場合、その鍵が必要な宝箱を"全部"開く」手順を繰り返した時、全部開けられる

証明は解説に任せるとして、最初に鍵の数をチェックしたら、以後は鍵が１個あれば全部開けるというのが面白い。
「ある鍵が１個しかないとき、複数の宝箱のどれを開けるか」を考えなくて良いので、非常に高速に開けられるか判定できる。

上記条件が高速で判定できることを利用すると、辞書順の開け順も簡単に求められる。
次に開ける候補を先頭の宝箱から順に選び、もしその宝箱を開けた場合、残りの宝箱・鍵がやはり全部開けられる状態なら、その箱を開ける。
その箱を先に開けてしまうと、残りの箱を全部開けられないなら、次の箱を開ける候補にする。
この手順を箱の数だけ繰り返せばよい。

int N,K;
int NK[201];
vector<int> key[201];
vector<int> k2v[201];
vector<int> mat[201];
vector<int> res;
int CK[201];
int op[201],vis[201];

int check(){
	int i,j;
	queue<int> Q;
	ZERO(vis);
	FOR(i,N) if(!op[i] && !vis[i] && CK[NK[i]]>0) {
		Q.push(i);
		vis[i]=1;
	}
	
	while(!Q.empty()) {
		int cur=Q.front();
		Q.pop();
		
		FOR(j,mat[cur].size()) {
			int tar=mat[cur][j];
			if(!op[tar] && !vis[tar]) {
				Q.push(tar);
				vis[tar]=1;
			}
		}
	}
	
	FOR(i,N) if(!op[i] && !vis[i]) return 0;
	return 1;
}

void solve(int _loop) {
	int i,x,y,z,j;
	
	GET2(&K,&N);
	ZERO(CK);
	FOR(i,K) CK[GETi()-1]++;
	FOR(i,201) {
		key[i].clear();
		k2v[i].clear();
		mat[i].clear();
	}
	
	FOR(i,N) {
		NK[i]=GETi()-1;
		k2v[NK[i]].push_back(i);
		key[i].resize(GETi());
		FOR(x,key[i].size()) key[i][x]=GETi()-1;
	}
	
	ZERO(mat);
	FOR(x,N) FOR(y,key[x].size())
		FOR(i,k2v[key[x][y]].size()) mat[x].push_back(k2v[key[x][y]][i]);
	
	_PE("Case #%d:",_loop);
	
	ZERO(op);
	if(check()==0) {
		_PE(" IMPOSSIBLE\n");
	}
	else {
		res.clear();
		
		FOR(x,N) {
			FOR(y,N) {
				if(op[y]) continue;
				if(CK[NK[y]]==0) continue;
				
				CK[NK[y]]--;
				FOR(i,key[y].size()) CK[key[y][i]]++;
				op[y]=1;
				if(check()==1) {
					res.push_back(y);
					break;
				}
				op[y]=0;
				FOR(i,key[y].size()) CK[key[y][i]]--;
				CK[NK[y]]++;
			}
			if(y==N) {
				_PE(" IMPOSSIBLE\n");
				return;
			}
		}
		
		FOR(x,res.size()) {_PE(" %d",res[x]+1);}
		_PE("\n");
	}
}

まとめ

うーん、この「鍵が足りてれば全部開けられる」って特性、本番だけでぱっと思いつくものなのかな…。
これ解ききった人は本番に思いついたのか、そういう特性を知ってたのか…。

この特性を知ってると簡単に解ける問題。