Codeforces #732 Div1 : C. AquaMoon and Permutations

こういうの聞かれるの珍しい印象。
https://codeforces.com/contest/1545/problem/C

問題

N*2Nの行列が与えられる。
各行は、1～Nの順列となっている。
これらは以下を満たす。

• それぞれの列は、互いに異なる。
• 2N行からあるN行を抽出した行列は、ラテン方陣を成す。

この状態で、以下を答えよ。

• 2N行からN行選ぶとき、ラテン方陣を成すのは何通りか。
• ラテン方陣を成す選び方を1個求めよ。

解法

ある列において、ある値が1回しか登場しない場合、その値を持つ行は必ず選ばれなければならない。
まずそのような行を抽出し、また同時に抽出できない行を取り除こう。
まだ選ぶ・選ばないが確定しない行が残っている場合、1個選ぶと連鎖的に選ぶ/選ばれない行がいくつか決定される場合がある。
そのような関係にある行同士の関係は、グラフでいうと偶閉路を成すので、閉路1個当たり2通りの選択肢が取れることになる。

int T,N;
int A[1005][505];
int B[505][505];
int alive[1010];
set<int> cand[505][505];
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			FOR(j,N) cand[i][j].clear();
		}
		FOR(i,2*N) alive[i]=1;
			
		FOR(y,2*N) {
			FOR(x,N) {
				cin>>A[y][x];
				A[y][x]--;
				cand[x][A[y][x]].insert(y);
			}
		}
		
		set<int> Q;
		vector<int> ret;
		ll pat=1;
		while(1) {
			int tar=-1;
			FOR(y,2*N) if(alive[y]) {
				FOR(x,N) if(cand[x][A[y][x]].size()==1) tar=y;
			}
			if(tar==-1) {
				FOR(y,2*N) if(alive[y]) break;
				if(y<2*N) {
					tar=y;
					pat=pat*2%mo;
				}
			}
			if(tar==-1) break;
			ret.push_back(tar);
			
			alive[tar]=0;
			set<int> del;
			FOR(x,N) {
				cand[x][A[tar][x]].erase(y);
				FORR(e,cand[x][A[tar][x]]) del.insert(e);
			}
			FORR(e,del) if(alive[e]==1) {
				alive[e]=0;
				FOR(i,N) cand[i][A[e][i]].erase(e);
			}
		}
		
		cout<<pat<<endl;
		FORR(v,ret) cout<<(v+1)<<" ";
		cout<<endl;
		
		
	}
}

まとめ

こういう問題、どうやると思いつくんだろ。