途中で抜けてしまった。
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の定理は思いついたものの、対角成分の並べ方にてこずってしまった。