AtCoder ABC #227 (キーエンスプログラミングコンテスト2021-Nov.) : H - Eat Them All

手間取った…。
https://atcoder.jp/contests/abc227/tasks/abc227_h

問題

3×3のグリッドがあり、それぞれ正整数が指定されている。
左上隅のセルから初めて、隣接セルを辿って元のセルに戻ることを考える。
各セルの訪問回数が、指定値になるような移動経路が存在するか判定せよ。

解法

まず、移動回数の条件を満たす経路を求めた後、それらが連結か判定する。
もし回数の条件を満たしたうえで連結なら、オイラー閉路が構築できるはずである。

移動回数の条件を考える。
セルを、左上セルが白になるように、白黒の市松模様に塗ることを考える。
黒セルから白セルへの移動は12通りあるが、うち4か所について移動回数を定めれば、残り8か所も移動回数が定まる。
そこで、4か所の移動回数を総当たりしてみよう。
この際、12通りの移動において、それぞれ1回でも通るかどうかを覚えておく。
各移動を1回でも行うかどうかは高々2^12通りなので、各パターンにおいて、12通りの移動回数を1例求めておこう。

白セルから黒セルも同様に計算しておく。

白セル→黒セルと、黒セル→白セルで、各移動経路を1回以上使うかどうかは2^24パターンあるので、これを総当たりしよう。
もしこれらにより全セル連結になるなら、上記の通り対応する移動回数に応じた有向辺を持つグラフを作り、オイラーパスを求めよう。

int A[3][3];

int U[3][3],D[3][3],L[3][3],R[3][3];

int pat[1<<12][4];
int did[1<<12];

template<int MV> class DirectedEulerPath {
public:
	int NV;
	vector<int> path;
	vector<int> E[MV];
	void add_path(int x,int y) { E[x].push_back(y);}
	
	void init(int NV){
		this->NV=NV;
		for(int i=0;i<NV;i++) E[i].clear();
		path.clear();
	}
	void dfs(int cur) {
		while(E[cur].size()) {
			int e=E[cur].back();
			E[cur].pop_back();
			dfs(e);
		}
		path.push_back(cur);
	}
	
	bool GetPath() {
		assert(NV);
		int te=0,i;
		FOR(i,NV) te += E[i].size();
		dfs(0);
		reverse(path.begin(),path.end());
		return path.size()==te+1;
	}
};


void go() {
	DirectedEulerPath<9> dep;
	dep.init(9);
	int y,x,i;
	FOR(y,3) FOR(x,3) {
		FOR(i,U[y][x]) dep.add_path(y*3+x,y*3+x-3);
		FOR(i,D[y][x]) dep.add_path(y*3+x,y*3+x+3);
		FOR(i,L[y][x]) dep.add_path(y*3+x,y*3+x-1);
		FOR(i,R[y][x]) dep.add_path(y*3+x,y*3+x+1);
	}
	if(dep.GetPath()) {
		string S;
		int i;
		FOR(i,dep.path.size()-1) {
			int d=dep.path[i+1]-dep.path[i];
			if(d==1) S+="R";
			if(d==3) S+="D";
			if(d==-1) S+="L";
			if(d==-3) S+="U";
		}
		cout<<S<<endl;
		exit(0);
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	MINUS(pat);
	
	ll S=0;
	FOR(y,3) FOR(x,3) {
		cin>>A[y][x];
		if((y+x)%2) S+=A[y][x];
		else S-=A[y][x];
	}
	if(S) {
		cout<<"NO"<<endl;
		return;
	}
	
	for(U[1][1]=0;U[1][1]<=A[1][1];U[1][1]++) {
		for(D[1][1]=0;U[1][1]+D[1][1]<=A[1][1];D[1][1]++) {
			for(L[1][1]=0;U[1][1]+D[1][1]+L[1][1]<=A[1][1];L[1][1]++) {
				R[1][1]=A[1][1]-U[1][1]-D[1][1]-L[1][1];
				for(R[0][0]=0;R[0][0]<=A[0][0];R[0][0]++) {
					int ok=1;
					L[0][2]=A[0][1]-R[0][0]-U[1][1];
					D[0][2]=A[0][2]-L[0][2];
					if(L[0][2]<0||D[0][2]<0) ok=0;
					U[2][2]=A[1][2]-D[0][2]-R[1][1];
					L[2][2]=A[2][2]-U[2][2];
					if(U[2][2]<0||U[2][2]<0) ok=0;
					R[2][0]=A[2][1]-L[2][2]-D[1][1];
					U[2][0]=A[2][0]-R[2][0];
					if(U[2][0]<0||R[2][0]<0) ok=0;
					D[0][0]=A[1][0]-U[2][0]-L[1][1];
					if(R[0][0]+D[0][0]!=A[0][0]) ok=0;
					if(ok) {
						int mask=0;
						if(R[0][0]) mask|=1<<0;
						if(D[0][0]) mask|=1<<1;
						if(L[0][2]) mask|=1<<2;
						if(D[0][2]) mask|=1<<3;
						if(U[2][2]) mask|=1<<4;
						if(L[2][2]) mask|=1<<5;
						if(U[2][0]) mask|=1<<6;
						if(R[2][0]) mask|=1<<7;
						if(U[2][2]) mask|=1<<8;
						if(D[2][2]) mask|=1<<9;
						if(L[2][2]) mask|=1<<10;
						if(R[2][2]) mask|=1<<11;
						pat[mask][0]=U[1][1];
						pat[mask][1]=D[1][1];
						pat[mask][2]=L[1][1];
						pat[mask][3]=R[0][0];
					}
				}
			}
		}
	}
	int m1,m2;
	FOR(m1,1<<12) if(pat[m1][0]>=0) {
		FOR(m2,1<<12) if(pat[m2][0]>=0) {
			int t=m1|m2;
			if(did[t]) continue;
			did[t]=1;

			U[1][1]=pat[m1][0];
			D[1][1]=pat[m1][1];
			L[1][1]=pat[m1][2];
			R[0][0]=pat[m1][3];
			R[1][1]=A[1][1]-U[1][1]-D[1][1]-L[1][1];
			L[0][2]=A[0][1]-R[0][0]-U[1][1];
			D[0][2]=A[0][2]-L[0][2];
			U[2][2]=A[1][2]-D[0][2]-R[1][1];
			L[2][2]=A[2][2]-U[2][2];
			R[2][0]=A[2][1]-L[2][2]-D[1][1];
			U[2][0]=A[2][0]-R[2][0];
			D[0][0]=A[1][0]-U[2][0]-L[1][1];
			
			D[0][1]=pat[m2][0];
			U[2][1]=pat[m2][1];
			R[1][0]=pat[m2][2];
			L[0][1]=pat[m2][3];
			L[1][2]=A[1][1]-D[0][1]-U[2][1]-R[1][0];
			R[0][1]=A[0][1]-L[0][1]-D[0][1];
			U[1][2]=A[0][2]-R[0][1];
			D[1][2]=A[1][2]-U[1][2]-L[1][2];
			R[2][1]=A[2][2]-D[1][2];
			L[2][1]=A[2][1]-R[2][1]-U[2][1];
			D[1][0]=A[2][0]-L[2][1];
			U[1][0]=A[1][0]-D[1][0]-R[1][0];
			go();
		}
	}
	
	
	cout<<"NO"<<endl;
}

まとめ

力業でやったのでコード量が増えるし、添え字のミスしたりしてしまった。
本番ACできてよかったね。