読者です 読者をやめる 読者になる 読者になる

SRM 563 Div1Hard

問題概要:

#.#..#.#
#..#.#.#
###.###.
#.#.####

こんな感じのボードのいくつかの空きますにコインを乗せる。傾けると1箇所場所が移動する。
壁にさえぎられていると動かない(一つのマスにどんどんコインが入ってくることも)、外に出たら落ちてしまう。
1つ以上落として1つ以上残したい。それが可能なコインの初期配置の個数は?

解法:


成り立たないものを考えて引き算しよう。
ダメそうなのは、全部いっぺんに落ちてしまうことしかできない、もしくは落とすことができない、とか。

大丈夫そうな組み合わせというのは、どちらか一方だけを落とすことができるコインの位置(a,b)みたいなのを最低1つ含んでいる。
まず、その「そこからどちらか一方だけを落とすことができるコインの位置の組」を求めることを考えるが、これは「片方だけ残った状態」から到達できる点の組すべてという感じである。壁で動かないということも考慮して3通りくらい場合わけがある。ここが一番面倒でO(N^2 M^2)かかる。

この点の組を辺だと思ってグラフを作ると、「ダメな組み合わせ」というのは「どの辺に対しても両方の頂点に当たる場所にコインがあるということは存在しない」ということと同値である。
でもそんなの求められるわけがないので、もう少し考える。
このグラフの補グラフを考えると、クリークがいくつかある形であるということが分かる。というのも、補グラフにおいて辺が存在するのは「コインの落とし方の集合」が完全に一致した場所同士であるということだから。また、異なるクリークの任意の頂点同士はすべて元のグラフ辺で結ばれているので、あるクリークに属するところでコインが存在してしまったら、もうほかのクリークの場所にコインは存在できない。また、クリーク内では好きなようにコインを選ぶことができる。(ただしどこにもコインを置かないというのが重複するので、クリークのサイズがnならそのクリークでの選び方は2^n - 1通りとなる。)

ということで2^(空いているマスの個数) - sum(クリークそれぞれ)(2^n - 1) - 1 が答えになる。

こういう非DP数え上げは得意だしほかの人はあんまり得意ではないらしいのでvery good. (といいつつBFS部分で落とした)

// I like wolves!!
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <string.h>
#include <complex>
using namespace std;

class CoinsGame {
	public:
	int bfs[45][45][45][45];
	int dx[4]={1,0,-1,0};
	int dy[4]={0,1,0,-1};
	int g[2000][2000];
	int v[2000];
	int mod=1000000009;
	int ways(vector <string> a) {
		int n=a.size();
		int m=a[0].size();
		queue<pair<pair<int,int>,pair<int,int> > > Q;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(a[i][j]=='#')continue;
				for(int k=0;k<n;k++){
					for(int l=0;l<m;l++){
						if(a[k][l]=='#')continue;
						bool ok=false;
						if(i==0){
							if(k!=0)ok=true;
						}
						if(i==n-1){
							if(k!=n-1)ok=true;
						}
						if(j==0){
							if(l!=0)ok=true;
						}
						if(j==m-1){
							if(l!=m-1)ok=true;
						}
						if(k==0){
							if(i!=0)ok=true;
						}
						if(k==n-1){
							if(i!=n-1)ok=true;
						}
						if(l==0){
							if(j!=0)ok=true;
						}
						if(l==m-1){
							if(j!=m-1)ok=true;
						}
						if(ok){
							bfs[i][j][k][l]=1;
							Q.push(make_pair(make_pair(i,j),make_pair(k,l)));
						}
					}
				}
			}
		}
		while(Q.size()){
			pair<int,int> fi=Q.front().first;
			pair<int,int> se=Q.front().second;
			int ff=fi.first;
			int fs=fi.second;
			int sf=se.first;
			int ss=se.second;
			Q.pop();
			for(int i=0;i<4;i++){
				//if(0<=ff+dx[i]&&ff+dx[i]<n&&0<=fs+dy[i]&&fs+dy[i]<m&&0<=sf+dx[i]&&sf+dx[i]<n&&0<=ss+dy[i]&&ss+dy[i]<m){
					if(0<=ff+dx[i]&&ff+dx[i]<n&&0<=fs+dy[i]&&fs+dy[i]<m&&0<=sf+dx[i]&&sf+dx[i]<n&&0<=ss+dy[i]&&ss+dy[i]<m&&!bfs[ff+dx[i]][fs+dy[i]][sf+dx[i]][ss+dy[i]]&&a[ff+dx[i]][fs+dy[i]]!='#'&&a[sf+dx[i]][ss+dy[i]]!='#'){
						bfs[ff+dx[i]][fs+dy[i]][sf+dx[i]][ss+dy[i]]=1;
						Q.push(make_pair(make_pair(ff+dx[i],fs+dy[i]),make_pair(sf+dx[i],ss+dy[i])));
					}
					if(0<=sf+dx[i]&&sf+dx[i]<n&&0<=ss+dy[i]&&ss+dy[i]<m&&0<=ff-dx[i]&&ff-dx[i]<n&&0<=fs-dy[i]&&fs-dy[i]<m&&!bfs[ff][fs][sf+dx[i]][ss+dy[i]]&&a[ff-dx[i]][fs-dy[i]]=='#'&&a[sf+dx[i]][ss+dy[i]]!='#'){
						bfs[ff][fs][sf+dx[i]][ss+dy[i]]=1;
						Q.push(make_pair(make_pair(ff,fs),make_pair(sf+dx[i],ss+dy[i])));
					}
					if(0<=ff+dx[i]&&ff+dx[i]<n&&0<=fs+dy[i]&&fs+dy[i]<m&&0<=sf-dx[i]&&sf-dx[i]<n&&0<=ss-dy[i]&&ss-dy[i]<m&&!bfs[ff+dx[i]][fs+dy[i]][sf][ss]&&a[ff+dx[i]][fs+dy[i]]!='#'&&a[sf-dx[i]][ss-dy[i]]=='#'){
						bfs[ff+dx[i]][fs+dy[i]][sf][ss]=1;
						Q.push(make_pair(make_pair(ff+dx[i],fs+dy[i]),make_pair(sf,ss)));
					}
				//}
			}
		}
			for(int i=0;i<n;i++)for(int j=0;j<m;j++)for(int k=0;k<n;k++)for(int l=0;l<m;l++){
				if(bfs[i][j][k][l]&&i*m+j!=k*m+l)g[i*m+j][k*m+l]=g[k*m+l][i*m+j]=1;
			}
	/*		for(int i=0;i<n*m;i++){
				for(int j=0;j<n*m;j++)printf("%d",g[i][j]);
				printf("\n");
			}*/
			long long ret=1;
			for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(a[i][j]=='.')ret=ret*2%mod;
			for(int i=0;i<n;i++)for(int j=0;j<m;j++){
				if(a[i][j]=='#')continue;
				if(v[i*m+j])continue;
				int c=0;
				for(int k=0;k<n;k++)for(int l=0;l<m;l++){
					if(a[k][l]=='#')continue;
					if(!g[i*m+j][k*m+l]){
						c++;
						v[k*m+l]=1;
					}
				}
				long long now=1;
			//	printf("%d\n",c);
				for(int k=0;k<c;k++)now=now*2%mod;
				now=(now+mod-1)%mod;
				ret=(ret+mod-now)%mod;
			}
			ret=(ret+mod-1)%mod;
			return ret;
		
	}
};

//Powered by [KawigiEdit] 2.0!