Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-26SRM360, SRM361 (Practice)

SRM 360 SumOfSelectedCells

|  SRM 360 SumOfSelectedCells - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 360 SumOfSelectedCells - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7875

  • editorial読んで実装。
    • 納得はした。
import java.util.HashSet;
import java.util.Set;

public class SumOfSelectedCells {
	static final String ok = "CORRECT";
	static final String ng = "INCORRECT";
	
	public int[][] rotate(int[][] tbl) {
		int w = tbl[0].length;
		int h = tbl.length;
		int[][] newtbl = new int[w][h];
		for (int i = 0 ; i < w ; i++) {
			for (int j = 0 ; j < h ; j++) {
				newtbl[i][j] = tbl[j][i];
			}
		}
		return newtbl;
	}
	
	public String hypothesis(String[] table) {
		int h = table.length;
		int w = table[0].split(" ").length;
		
		int[][] number = new int[h][w];
		for (int i = 0 ; i < h ; i++) {
			String[] l = table[i].split(" ");
			for (int j = 0 ; j < w ; j++) {
				int val = Integer.valueOf(l[j]);
				number[i][j] = val;
			}
		}
		if (h < w) {
			number = rotate(number);
			int t = w;
			w = h;
			h = t;
		}
		
		if (h != w) {
			for (int i = 0 ; i < w ; i++) {
				Set<Integer> set = new HashSet<Integer>();
				for (int j = 0 ; j < h ; j++) {
					set.add(number[j][i]);
				}
				if (set.size() >= 2) {
					return ng;
				}
			}
			return ok;
		} else {
			for (int i = 0 ; i < w ; i++) {
				for (int j = 0 ; j < h ; j++) {
					for (int k = i+1 ; k < w ; k++) {
						for (int l = j+1 ; l < h ; l++) {
							if (number[j][i] + number[l][k] != number[l][i] + number[j][k]) {
								return ng;
							}
						}
					}					
				}
			}
			return ok;
		}
	}
}