AOJ 2573: Overwriting Game

ブログに記事を書きます Advent Calendar 2014 - Adventar13日目。

許すまじ物理ゲー。せめて公式くらい書かないと単なる出題ミス。
そしてそれに加えてYes/Noによる難デバッグ化と変な罠ケースで本当に嫌がらせのために問題作ったとしか思えない。
難易度はつけようがないと思う。

本質はどこへ行った。

上に書いたことはこの問題についてのコメントではなく、White Birdに対する言及です。

この問題に対するコメントはここからはじまります。

5*5のうち、

• • • • #
    • ##
    • ##
  • ###

#####
みたいな#であらわせる領域の個数は252個。これらが正しく塗られている状態を変数に持って連立方程式を立てればよい。

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
const double EPS=1e-8;
typedef vector<double>vec;
typedef vector<vec>mat;
inline double ABS(double a){return max(a,-a);}
vec gauss_jordan(const mat &A,const vec &b){
	int n=A.size();
	mat B(n,vec(n+1));
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)B[i][j]=A[i][j];
	for(int i=0;i<n;i++)B[i][n]=b[i];
	for(int i=0;i<n;i++){
		int pivot=i;
		for(int j=i;j<n;j++){
			if(ABS(B[j][i])>ABS(B[pivot][i]))pivot=j;
		}
		swap(B[i],B[pivot]);
		if(ABS(B[i][i])<EPS)break;
		for(int j=i+1;j<=n;j++)B[i][j]/=B[i][i];
		for(int j=0;j<n;j++){
			if(i!=j){
				for(int k=i+1;k<=n;k++)B[j][k]-=B[j][i]*B[i][k];
			}
		}
	}
	vec x(n);
	for(int i=0;i<n;i++)x[i]=B[i][n];
	return x;
}
char sA[7][7];
char sB[7][7];
vector<int>v[400];
map<vector<int>,int>m;
int sz;
int perm[7];
int h,w;
void calc(int a,int b){
	if(a==h){
		vector<int>tmp;
		for(int j=0;j<a;j++)tmp.push_back(perm[j]);
		v[sz]=tmp;
		m[tmp]=sz++;
		return;
	}
	for(int i=b;i<=w;i++){
		perm[a]=i;
		calc(a+1,i);
	}
}
int t[7][7];
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a){
		h=a;w=b;
		for(int i=0;i<a;i++)scanf("%s",sA+i);
		for(int i=0;i<a;i++)scanf("%s",sB+i);
		m.clear();
		sz=0;
		calc(0,0);
		//printf("%d\n",sz);
		mat A(sz,vec(sz));
		vec B(sz);
		for(int i=0;i<sz;i++){
			if(v[i][0]==w){
				A[i][i]=1;
				continue;
			}
			A[i][i]=a*b*2;
			for(int j=1;j<=a;j++)for(int k=1;k<=b;k++){
				B[i]+=j*k;
				for(int x=0;x<a;x++)for(int y=0;y<b;y++)t[x][y]=0;
				for(int l=0;l<a;l++)for(int o=0;o<v[i][l];o++)t[l][b-1-o]=1;
				for(int x=0;x<j;x++)for(int y=0;y<k;y++){
					if(sB[x][y]=='B')t[x][y]=1;
					else t[x][y]=0;
				}
				vector<int>to(a);
				for(int l=a-1;l>=0;l--){
					int r=0;
					for(int o=b-1;o>=0;o--){
						if(!t[l][o])break;
						r++;
					}
					if(l<a-1)r=min(r,to[l+1]);
					to[l]=r;
				}
				int tv=m[to];
				A[i][tv]-=1;
			}
			for(int j=1;j<=a;j++)for(int k=1;k<=b;k++){
				B[i]+=j*k;
				for(int x=0;x<a;x++)for(int y=0;y<b;y++)t[x][y]=0;
				for(int l=0;l<a;l++)for(int o=0;o<v[i][l];o++)t[l][b-1-o]=1;
				for(int x=0;x<j;x++)for(int y=0;y<k;y++){
					if(sB[x][y]=='W')t[x][y]=1;
					else t[x][y]=0;
				}
				vector<int>to(a);
				for(int l=a-1;l>=0;l--){
					int r=0;
					for(int o=b-1;o>=0;o--){
						if(!t[l][o])break;
						r++;
					}
					if(l<a-1)r=min(r,to[l+1]);
					to[l]=r;
				}
				int tv=m[to];
				A[i][tv]-=1;
			}
		}
	//	for(int i=0;i<sz;i++){
		//	for(int j=0;j<sz;j++)printf("%.2f ",A[i][j]);
	//		printf("%.2f\n",B[i]);
		//}
		vec x=gauss_jordan(A,B);
		
		vector<int>ans(a);
		for(int i=a-1;i>=0;i--){
			int r=0;
			for(int j=b-1;j>=0;j--){
				if(sB[i][j]!=sA[i][j])break;
				r++;
			}
			if(i<a-1)r=min(r,ans[i+1]);
			ans[i]=r;
		}
		printf("%.12f\n",x[m[ans]]);
	}
}

*1

*1:ところであの超絶悪問、点数をつけるとしたら解法は500もないはずで、じゃあなんで800かという問題を考えさせられる。