メンバー/SGHR/topcoder/ApplesAndPears - 阪大理学部科学計算・開発サークル -Circle for Science Caluculation and Development-

問題

ジャンル

全探索

解説

格子状のテーブルの上のりんご(Apple)となし(Pear)の並びが与えられ、K回以内の並べ替えでりんごまたはなしまたは空で埋め尽くせる最大の長方形の面積を求めよ、という問題。
例えば下のような初期状態でK=3のとき

	P	P
P	P	A
P	A	P

3回の並べ替えで

P	P	P
P	P	P
	A	A

とするのが最大で、このときなしで埋め尽くされた長方形の面積は6となる。

一見どこから手をつければいいかわからない問題であるがアルゴリズムは単純で、考えうる全ての長方形について

1. そこに含まれるりんご、なし、空の数を数える。
2. K回以内の並べ替えでりんご、なし、空で埋め尽くせるか判定する。
3. 埋め尽くせる場合はその長方形の面積をSmaxとして更新する。

とすればよく、計算量はO(n^4)である。

見た目は複雑そうだがアルゴリズムは単純な良問。

コード

#include<cmath>
#include<cstdlib>
#include<sstream>
#include<string>
#include<vector>
#include<iostream>
#include<queue>
#include<deque>
#include<stack>
#include<list>
#include<map>
#include<algorithm>
using namespace std;
 
#define MAX_N 51
 
class ApplesAndPears{
public:
  map<char, vector< vector<int> > > ref;
 
  int rect(char c, int x0, int y0, int x1, int y1){
    vector< vector<int> > table = ref[c];
    return table[x1][y1] - table[x1][y0] - table[x0][y1] + table[x0][y0];
  }
 
  int getArea(vector <string> board, int K){
    int n = board.size();
    vector< vector<int> > table;
    table.resize(MAX_N);
    for(int i=0; i<MAX_N; i++) table[i].resize(MAX_N);
    ref.insert(map<char, vector< vector<int> > >::value_type('A', table));
    ref.insert(map<char, vector< vector<int> > >::value_type('P', table));
    ref.insert(map<char, vector< vector<int> > >::value_type('.', table));
 
    for(int x=0; x<=n; x++){
      int a = 0;
      int p = 0;
      int e = 0;
      for(int y=0; y<=n; y++){
	if(x == 0 || y == 0){
	  ref['A'][x][y] = 0;
	  ref['P'][x][y] = 0;
	  ref['.'][x][y] = 0;
	}
	else{
	  if(board[x-1][y-1] == 'A') a++;
	  if(board[x-1][y-1] == 'P') p++;
	  if(board[x-1][y-1] == '.') e++;
	  ref['A'][x][y] = a + ref['A'][x-1][y];
	  ref['P'][x][y] = p + ref['P'][x-1][y];
	  ref['.'][x][y] = e + ref['.'][x-1][y];
	}
      }
    }
 
    int A = rect('A', 0, 0, n, n);
    int P = rect('P', 0, 0, n, n);
    int E = rect('.', 0, 0, n, n);
    int ans = 0;
    for(int x0=0; x0<=n-1; x0++){
      for(int y0=0; y0<=n-1; y0++){
	for(int x1=x0+1; x1<=n; x1++){
	  for(int y1=y0+1; y1<=n; y1++){
	    int S = (x1 - x0) * (y1 - y0);
	    int a = rect('A', x0, y0, x1, y1);
	    int p = rect('P', x0, y0, x1, y1);
	    int e = rect('.', x0, y0, x1, y1);
	    if(S <= A && 2*p+e <= K && (p == 0 || E > 0)) ans = max(ans, S);
	    if(S <= P && 2*a+e <= K && (a == 0 || E > 0)) ans = max(ans, S);
	    if(S <= E && a+p <= K) ans = max(ans, S);
	  }
	}
      }
    }
    return ans;
  }
};