SRM 360 250pt : SumOfSelectedCells

問題概要

二次元の整数テーブルが与えられる。同じ行、列からはひとつずつしかとらない、という制約の元でできるだけ多くマスを選ぶ。どのように選んでもマスに書かれた数字の和が等しくなるかどうか判定する問題。

解法

テーブルが正方形の時はPOJで解いた記憶がある。各行の階差数列が同じになっているか調べればよい。テーブルが長方形の時は、長い方が全て同じ数値であるかどうかも確かめなければならない。

#include <vector>
#include <set>
#include <string>
#include <sstream>
using namespace std;

struct SumOfSelectedCells {

	string hypothesis(vector <string> table) {
		int N = table.size();
		vector< vector<int> > ass(N);
		for(int i=0; i<N; i++){
			stringstream ss(table[i]);
			int t;
			while(ss>>t){
				ass[i].push_back(t);
			}
		}
		int M = ass[0].size();
		if(N==1 || M==1){
			int a = ass[0][0];
			for(int i=0; i<N; i++)for(int j=0; j<M; j++){
				if(ass[i][j] != a) return "INCORRECT";
			}
			return "CORRECT";
		}

		if(N > M){
			vector< vector<int> > tmp = ass;
			ass = vector<vector<int> >(M, vector<int>(N));
			for(int i=0; i<N; i++)for(int j=0; j<M; j++){
				ass[j][i] = tmp[i][j];
			}
			swap(N,M);
		}

		set<vector<int> > vs;
		for(int i=0; i<N; i++){
			vector<int> t;
			int prev = ass[i][0];
			for(int j=1; j<M; j++){
				t.push_back(ass[i][j] - prev);
				prev = ass[i][j];
			}
			vs.insert(t);
		}

		if((int)vs.size()>1){
			return "INCORRECT";
		}
		if(M > N){
			vector<int> t = *vs.begin();
			for(int i=0; i<(int)t.size(); i++)if(t[i]!=0) return "INCORRECT";
		}
		return "CORRECT";
	}

};