KUPC 2011 I: 山 - komiyamの日記

問題概要

行列(W,H<1000)があって、各マスには互いに異なる数字が入っている。行のスワップ、列のスワップを行うことにより、行列がある制限を満たすようにできるかどうか判定する問題。制限は、最大要素から離れるほど値が小さくなっていること。

考えたこと

行と列が独立していることはすぐに気づく。嘘です本当は5分くらい気づきませんでした。
ベクトルの配列だと思えば良い。任意のiに対してa[i]
そうなっているとき右の子か左の子にくっつけていけば良いのかな?
サンプル合ったので投げてみる。1ケースだけ落ちてる。
でもテストケース弱いのでリジャッジしますとか告知されてるし、何か間違ってるんだろう。
右の子にも左の子にもくっつけられるときどうすればいいんだろう。
どっちにくっつけるかランダムにしてみようかなあ(二匹目のドジョウ)。
でも試行回数が増やせないので多分それだとダメだ。今回は落ちてるの１ケースだけだからseed変えるだけで何とかなるかも知れないけど、リジャッジでより厳しいテストケースが増えるし。
グラフを書いてみる。すぐにDAGの最小パス被覆であることに気づいた。嘘です本当は10分くらい気づきませんでした
ただし、DAGの構成に時間がかかる。トポロジカル順序だけなら単純に辞書順比較でソートするだけで得られるけど。

上の図から想像されるような枝刈りをした(何のこっちゃ)。
- 後から考えたことだけど、これだと全てが孤立点であるようなグラフでは枝刈りできない。なので、極小値が2つ以上あることが発覚した時点で無理と答えるような処理を加えなければいけなかった。
2部マッチングのライブラリをコピペして送信。リジャッジの影響で結果待ちが長い。
待っている間に例外を考慮しきれていない場合に気づいた。

上の図だとDAGの最小パス被覆が2以下だけど山にはならない。
最大元が存在することを確認する処理を加えて再提出。その後しばらく待っていたらリジャッジが終わっていて通ってた。

本番中に通ったコード

//各行、各列ごとに分けて考える
//最大元が存在する、かつ最小パス被覆が2以下かどうかを判定すれば良い

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_W = 1009;
const int INF = 1<<29;
int H, W;

bool graph[MAX_W][MAX_W];

int nums[MAX_W][MAX_W];
int tmp[MAX_W][MAX_W];
vector<int> X[MAX_W];

//A > Bかどうか
bool cmp_v(const vector<int>& a, const vector<int>& b){

	for(int i=0; i<W; i++){
		if(a[i] < b[i]) return false;
	}

	return true;
}

bool solve(){
	for(int i=0; i<H; i++){
		X[i].clear();
	}

	int maxi = -1, key = -1;
	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			if(maxi < nums[i][j]){
				maxi = nums[i][j];
				key = i;
			}
		}
	}

	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			X[i].push_back(nums[i][j]);
		}
	}

	vector<int> best_vec = X[key];

	sort(X, X+H);
	reverse(X, X+H);

	for(int j=1; j<H; j++){
		if( !cmp_v(X[0], X[j]) ){
			return false;
		}
	}

	//DAGをつくる
	V = 2*H;
	for(int i=0; i<V; i++){
		G[i].clear();
	}
	
	memset(graph, 0, sizeof(graph));
	for(int i=H-1; i>=0; i--){
		for(int j=i+1; j<H; j++)if( !graph[i][j] ){
			if( cmp_v(X[i], X[j]) ){
				graph[i][j] = true;
				add_edge(i, j+H);
				for(int k=0; k<H; k++){
					graph[i][k] |= graph[j][k];
				}
			}
		}
	}

	if(best_vec != X[0]){
		return false;
	}

	return (H - bipartite_matching()) <= 2;
}

bool sub_solve(){

	if(!solve()){
		return false;
	}

	//swap処理
	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			tmp[j][i] = nums[i][j];
		}
	}

	swap(H, W);
	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			nums[i][j] = tmp[i][j];
		}
	}

	return solve();

}

int main(){

	scanf("%d%d",&H, &W);
	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			scanf("%d", nums[i]+j);
		}
	}

	bool ans = sub_solve();

	puts(ans?"YES":"NO");

	return 0;
}