AOJ1117 Missing Numbers

AOJ Volume11

問題リンク Missing Numbers

  • 概要

(p+1)行(s+1)列からなる売上表がある。各行のs+1列目はその行の売上合計、各列のp+1行目はその列の売上合計を表す。
売上表の一部が欠損しており復元したい。復元の仕方がただ1通りに求まるならば復元し、復元方法が複数あったり不可能な場合は"NO"と答えよ。なお、売上には赤字もあるため、負の値があっても構わない。また、売上は整数でなければならない。
以下のことが保証されている
合計を表す列、行に欠損はない
入力には必ず1か所以上の欠損がある
　p < 100
　s < 10
　-1000 <= 売上 <= 1000
　-100000 <= 売上合計 <= 100000

  • 解法

欠損箇所に入れる数字の候補が無限にあるため、アプローチしづらい問題だと感じましたが、貪欲法で解くことができました。
基本に立ち直って、ある列か行に、欠損箇所が1つしかない場所があったら、その箇所は決定することができます。これを繰り返します。繰り返しの結果、表が全部埋まったら解となります。
では、表が埋まり切らなかった場合、つまり欠損箇所がある行と列全てが2か所以上の欠損箇所を持っている場合、実はこれはサンプル2の例と合致している状況で、復元方法が一意に定まらなくなっています。連立方程式を作ってみても解が一意に出てきません。
結局、確定するセルを埋めていって、埋めきったら解、駄目だったら"NO"となります。

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

//Missing Numbers
public class AOJ1117 {

	class R implements Comparable<R>{
		boolean row;
		int p, c;
		public R(boolean row, int p, int c) {
			this.row = row;
			this.p = p;
			this.c = c;
		}
		public int compareTo(R o) {
			return c-o.c;
		}
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		int NOT = 1<<29;
		for(boolean head=true;;head=false){
			int h = sc.nextInt();
			if(h==0)break;
			int w = sc.nextInt();
			if(!head)System.out.println();
			int[][] a = new int[h+1][w+1];
			boolean[][] m = new boolean[h+1][w+1];
			for(int i=0;i<=h;i++)for(int j=0;j<=w;j++){
				String s = sc.next();
				m[i][j] = "?".equals(s);
				if(m[i][j])a[i][j]=NOT;
				else a[i][j]=Integer.parseInt(s);
			}
			boolean ok = false;
			for(;;){
				PriorityQueue<R> q = new PriorityQueue<R>();
				int[] rc = new int[h], cc = new int[w];
				for(int i=0;i<h;i++)for(int j=0;j<w;j++){
					if(a[i][j]==NOT){
						rc[i]++; cc[j]++;
					}
				}
				for(int i=0;i<h;i++)if(0<rc[i])q.add(new R(true, i, rc[i]));
				for(int j=0;j<w;j++)if(0<cc[j])q.add(new R(false, j, cc[j]));
				if(q.isEmpty()){
					ok = true; break;
				}
				R r = q.poll();
				if(2<=r.c)break;
				if(r.row){
					int pj = -1, v = a[r.p][w];
					for(int j=0;j<w;j++){
						if(a[r.p][j]==NOT)pj = j;
						else v-=a[r.p][j];
					}
					a[r.p][pj] = v;
				}
				else{
					int pi = -1, v = a[h][r.p];
					for(int i=0;i<h;i++){
						if(a[i][r.p]==NOT)pi = i;
						else v-=a[i][r.p];
					}
					a[pi][r.p] = v;
				}
			}
			if(ok){
				for(int i=0;i<h;i++)for(int j=0;j<w;j++)if(m[i][j])System.out.println(a[i][j]);
			}
			else System.out.println("NO");
		}
	}

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