TopCoder SRM 806 : Div1 Easy Div2 Hard TransposeColors

なんとかレート増で良かった。
https://community.topcoder.com/stat?c=problem_statement&pm=16990&rd=18686

問題

正整数Nが与えられる。
N*Nのグリッドにおいて、R行C列目には整数Rが書かれている。
また、このN*Nマスに加え、あと1つ空きマスがあるものとする。

(初期空きマスを含め)任意のセルを選び、その値をその時点での空きマスに移動する、という処理を繰り替えす。
その結果、R行C列目には整数Cが書かれているようにしたい。
最短の手順を求めよ。

解法

N点の有向グラフを考える。
各セルについて、初期状態でRが書かれており、最終的に異なる値Cに遷移したいなら、R→Cと有向辺を張ろう。
あとは、このグラフについてオイラー閉路を求めれば、閉路に沿って空きマスへの移動を繰り返せば条件を満たせる。

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;
		vector<int> deg(NV);
		FOR(i,NV) {
			te += E[i].size();
			deg[i]+=E[i].size();
			FORR(e,E[i]) deg[e]--;
		}
		int d0=0,s=0;
		FOR(i,NV) {
			if(deg[i]>1 || deg[i]<-1) return false;
			if(deg[i]==0) d0++;
			if(deg[i]==1) s=i;
		}
		if(d0!=NV && d0+2!=NV) return false;
		dfs(s);
		reverse(path.begin(),path.end());
		return path.size()==te+1;
	}
};

int A[44][44];

class TransposeColors {
	public:
	vector <int> move(int N) {
		DirectedEulerPath<80> ep;
		if(N==1) return {};
		
		int x,y;
		FOR(x,N) FOR(y,N) A[y][x]=y;
		
		ep.init(N);
		FOR(y,N) FOR(x,N) if(x!=y) {
			ep.add_path(x,y);
		}
		assert(ep.GetPath());
		vector<int> V=ep.path;
		vector<int> ret;
		
		
		int i;
		int B=A[V[0]][V[1]];
		
		ret.push_back(V[0]*N+V[1]);
		
		for(i=1;i<V.size()-1;i++) {
			ret.push_back(V[i]*N+V[i+1]);
			A[V[i-1]][V[i]]=A[V[i]][V[i+1]];
		}
		ret.push_back(N*N);
		A[V[V.size()-2]][V[V.size()-1]]=B;
		
		FOR(y,N) {
			FOR(x,N) cout<<A[y][x]<<" ";
			cout<<endl;
		}
			
		
		
		return ret;
		
	}
}

まとめ

ちょっとオーバースペックな解法だった。