SRM 466 Div2 Hard MatrixGame

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=10861&rd=14150

'1'か'0'を要素に持つvector string が与えられる。行か列の交換を好きなだけ行なって辞書順最小のものを返せ。

やりかた

まず列の入れ替え方を全順列で試してみて、その中で行の入れ替えはソートで行う。そうして全順列中で辞書順最小のものを取る。

以下ソース。

class MatrixGame {
public:
  vector <string> getMinimal(vector <string> matrix) {
    vector <string> result = matrix;
    int H = matrix.size();
    int W = matrix[0].size();

    int num[10];
    for(int i = 0; i < W; i++) num[i] = i;
    do{
      vector<string> cur = matrix;
      for(int i = 0; i < H; i++)
	for(int j = 0; j < W; j++)
	  cur[i][j] = matrix[i][num[j]];
      sort(ALL(cur));
      if(result > cur) result = cur;
    }while(next_permutation(num, num + W));
    return result;
  }
};

これができないのはまずかったなあ。

SRM 464, 465はまた後日。