kmjp's blog

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

Google Code Jam 2020 Qualification Round : E. Indicium

GCJ

途中で抜けてしまった。
https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209aa0

問題

整数N,Kが与えられる。
1～Nで構成されるラテン方陣のうち、対角成分の和がKとなるものを1つ構築せよ。

解法

構築できないケースを考える。
N個の対角成分のうち(N-1)要素が同じ値で、あと1個が異なるとき、構築不可である。
こうなるのは、K=N+1またはK=N^2-1または(N,K)=(3,5),(3,7)の時である。
それ以外は構築可能である。

N=2の時はK=2,4の時点で明らか。以後Nが3以上の時を考える。
対角成分がAAAABCのようにAが(N-2)個、B,Cが1個の時を考える。
なお、A=CかつA!=Bのように同じ値が(N-1)個並んでしまうケースは不可。B＝CやA=B=Cは問題ない。

この時、まずこのA,B,Cの3値だけラテン方陣を組むよう頑張って並べよう。
そうすると、各行・各列(N-1)～(N-3)個の値が未確定になる。
ここに使ってない値を順に埋めていく。
行と列を左右の頂点とし、値の埋まってないセルを辺とする二部グラフを考える。
ここで未確定の数の回数だけ、容量Nのフローを流し、それぞれ使った辺に対応する列に値を埋めて行こう。
Hallの結婚定理より、この埋め方は常に問題ない。

行ごとや列ごとに埋めようとすると、（偶然うまくいく場合もあるが）失敗することもあるので注意。

template<class V> class MaxFlow_Ford {
public:
	struct edge { int to,reve;V cap;};
	static const int MV = 102;
	vector<edge> E[MV];
	vector<int> path;
	int vis[MV];
	void add_edge(int x,int y,V cap,bool undir=false) {
		E[x].push_back((edge){y,(int)E[y].size(),cap});
		E[y].push_back((edge){x,(int)E[x].size()-1,undir?cap:0});
	}
	V dfs(int from,int to,V cf) {
		V tf;
		path.push_back(from);
		if(from==to) return cf;
		vis[from]=1;
		FORR(e,E[from]) if(vis[e.to]==0 && e.cap>0 && (tf = dfs(e.to,to,min(cf,e.cap)))>0) {
			e.cap -= tf;
			E[e.to][e.reve].cap += tf;
			return tf;
		}
		path.pop_back();
		return 0;
	}
	V maxflow(int from, int to) {
		V fl=0,tf;
		while(1) {
			ZERO(vis);
			path.clear();
			if((tf = dfs(from,to,numeric_limits<V>::max()))==0) return fl;
			fl+=tf;
		}
	}
};

int N,K;
int A[51][51];

int from[2551][51];
int num[2551][51];

void out(int _loop) {
	int y,x;
	_P("Case #%d: POSSIBLE\n",_loop);
	FOR(y,N) {
		FOR(x,N) {
			_P("%d",A[y][x]);
			if(x<N-1) _P(" ");
		}
		_P("\n");
	}
}

void solve(int _loop) {
	int f,i,j,k,l,x,y,z;
	ZERO(A);
	
	cin>>N>>K;
	
	if(N==2) {
		if(K==3) {
			_P("Case #%d: IMPOSSIBLE\n",_loop);
			return;
		}
		if(K==2) A[0][0]=A[1][1]=1,A[0][1]=A[1][0]=2;
		if(K==4) A[0][0]=A[1][1]=2,A[0][1]=A[1][0]=1;
		out(_loop);
		return;
	}
	
	int ox=0,oy=0,oz=0;
	for(x=1;x<=N;x++) {
		for(y=1;y<=N;y++) {
			for(z=1;z<=N;z++) {
				if(x==y&&x!=z) continue;
				if(x==z&&x!=y) continue;
				if(N==3&&y==z&&x!=y) continue;
				if(x*(N-2)+y+z==K) ox=x,oy=y,oz=z;
			}
		}
	}
	
	if(ox==0) return _P("Case #%d: IMPOSSIBLE\n",_loop);
	if(ox==oy&&oz==oy) {
		FOR(y,N) {
			FOR(x,N) {
				A[y][(y+x)%N]=ox+x;
				if(A[y][(y+x)%N]>N) A[y][(y+x)%N]-=N;
			}
		}
		out(_loop);
		return;
	}
	
	int ng[52][52]={};
	FOR(i,N-2) A[i][i]=ox;
	A[N-1][N-2]=A[N-2][N-1]=ox;
	if(oy==oz) {
		FOR(i,N-2) A[(i+1)%(N-2)][i]=oy;
		A[N-1][N-1]=A[N-2][N-2]=oy;
	}
	else {
		FOR(i,N-2) A[(N-1+i)%N][i]=oy;
		A[N-2][N-2]=A[N-3][N-1]=oy;
		FOR(i,N-2) A[i+1][i]=oz;
		A[N-1][N-1]=A[0][N-2]=oz;
	}
	ox--,oy--,oz--;
	
	
	while(1) {
		for(i=1;i<=N;i++) {
			FOR(x,N) if(A[0][x]==i) break;
			if(x==N) break;
		}
		if(i==N+1) break;
		MaxFlow_Ford<int> mf;
		FOR(y,N) {
			mf.add_edge(2*N,y,1);
			mf.add_edge(N+y,2*N+1,1);
			FOR(x,N) if(A[y][x]==0) mf.add_edge(y,x+N,1);
		}
		x=mf.maxflow(2*N,2*N+1);
		FOR(y,N) {
			FORR(e,mf.E[y]) {
				if(e.to>=N&&e.to<2*N&&e.cap==0) A[y][e.to-N]=i;
			}
		}
	}

	out(_loop);	
}

まとめ

本番Hallの定理は思いついたものの、対角成分の並べ方にてこずってしまった。