yukicoder : No.918 LISGRID

今回は時間通りに参加できず。
https://yukicoder.me/problems/no/918

問題

H*Wのグリッドの各マスに、1～(HW)の整数を1個ずつ埋めることを考える。
H要素の整数列Sと、W要素の整数列Tが与えられる。

各行のマスを左から順に見た数列におけるLIS長を並べ替えたものがSと一致し、各列のマスを上から順に見た数列におけるLIS長を並べ替えたものがTと一致するような数値の埋め方を構成せよ。

解法

S,Tをともに降順に並べておき、各行・各列のLIS長はこのS,Tに合うようにする。
各行・列におけるLIS長がkの時、最初のk要素は単調増加で、以降は単調減少にすることを考える。

セルに対応する頂点を持つ有向グラフを考える。
隣接セルの大小関係に対応して有向辺を張ろう。
このグラフは閉路を持たないので、トポロジカルソートすれば条件に反しない数字の埋め方が求められる。

int H,W;
int A[404],B[404];

vector<int> E[202020];
int in[202020];
int M[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(i,H) cin>>A[i];
	FOR(i,W) cin>>B[i];
	sort(A,A+H);
	reverse(A,A+H);
	sort(B,B+W);
	reverse(B,B+W);
	
	FOR(y,H) {
		for(x=1;x<W;x++) {
			if(x<A[y]) {
				E[y*W+x].push_back(y*W+x-1);
				in[y*W+x-1]++;
			}
			else {
				E[y*W+x-1].push_back(y*W+x);
				in[y*W+x]++;
			}
		}
	}
	FOR(x,W) {
		for(y=1;y<H;y++) {
			if(y<B[x]) {
				E[y*W+x].push_back(y*W+x-W);
				in[y*W+x-W]++;
			}
			else {
				E[y*W+x-W].push_back(y*W+x);
				in[y*W+x]++;
			}
		}
	}
	
	int nex=H*W;
	queue<int> Q;
	FOR(i,H*W) if(in[i]==0) Q.push(i);
	while(Q.size()) {
		i=Q.front();
		Q.pop();
		M[i]=nex--;
		
		FORR(e,E[i]) if(--in[e]==0) Q.push(e);
	}
	
	FOR(y,H) {
		FOR(x,W) cout<<M[y*W+x]<<" ";
		cout<<endl;
	}
	
}

まとめ

トポロジカルソートを使わず直接構成することできるのかな。