AOJ-2208: トーマス・ライトの憂鬱

keyword

Greedy　Java

問題概要

N*N(N<10000)のboolean行列の、各行、各列の1の個数が与えられる。行列が一意に復元できるかどうか判定する問題。

解法

Greedyにやってみたら上手くいった。上手くいった理由は分からない。

import java.util.*;
import static java.util.Arrays.*;

public class Main {

	int[] xs, ys;

	void run(){
		Scanner in = new Scanner(System.in);
		for(;;){
			int N = in.nextInt();
			if(N == 0) return ;
			xs = new int[N];
			ys = new int[N];
			for(int i=0; i<N; i++){
				xs[i] = in.nextInt();
			}
			for(int i=0; i<N; i++){
				ys[i] = in.nextInt();
			}
			System.out.println(solve()?"Yes":"No");
		}
	}

	boolean solve(){
		int N = xs.length;
		int px = 0, qx = N-1;
		int py = 0, qy = N-1;
		int putX = 0, putY = 0;
		sort(xs);
		sort(ys);
		for(;;){
			int X = qx - px + 1, Y = qy - py + 1;
			if(X>0 && xs[px] == putY){
				px++;
			}
			else if(X>0 && xs[qx] == Y + putY){
				qx--;
				putX++;
			}
			else if(Y>0 && ys[py] == putX){
				py++;
			}
			else if(Y>0 && ys[qy] == X + putX){
				qy--;
				putY++;
			}
			else{
				return X==0 && Y==0;
			}
		}
	}

	public static void main(String args[]){
		new Main().run();
	}
}