AOJ2208 The Melancholy of Thomas Right

AOJ Volume22

問題リンク The Melancholy of Thomas Right

  • 解法

列や行は入れ替えても構いません。よって、数字の並びをソートしても構わないことになります。
ここであることに気づきます。以下は行と列をソートした後のサンプル3です。

0 1 1 2 5 5 5 8 8 9
0
1 o
3 o o o
3 o o o
3 o o o
6 o o o o o o
6 o o o o o o
6 o o o o o o
7 o o o o o o o
9 o o o o o o o o o

行の下の段からoを埋めることを考えると、行の数字と、oを入れることができる列の個数が常に一致します。逆に、サンプル2の場合はこれが成り立ちません。
よってこのチェックをすることでYesかNoかが分かります。

  • ソース
import java.util.Arrays;
import java.util.Scanner;

//The Melancholy of Thomas Right
public class AOJ2208 {

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			int[] a = new int[n], b = new int[n];
			for(int i=0;i<n;i++)a[i]=sc.nextInt();
			for(int i=0;i<n;i++)b[i]=sc.nextInt();
			Arrays.sort(a);
			Arrays.sort(b);
			int t = 0, c = 0;
			while(t<n&&a[t]==0)t++;
			boolean f = true;
			for(int i=n-1;i>=0;i--){
				if(n-t!=b[i]){
					f = false; break;
				}
				c++;
				while(t<n&&a[t]<=c)t++;
			}
			System.out.println(f?"Yes":"No");
		}
	}
	
	public static void main(String[] args) {
		new AOJ2208().run();
	}
}