SRM 513 Div2 1000pt: CutTheNumbers

TopCoder

問題概要

W*H(W,H<=4)のボードが与えられて、各セルには0~9までの数字が埋まっている。これを幅か高さが1の断片に分ける。各断片に書かれた数字を上から(or左から)読んで和を取るとき、作れる和の最大値を求める問題。

考えたこと

  • 今年のICPCのE問題(輪番停電のアレ)と一緒？
  • サイズがやたら小さいというか、2^16臭がするけどそんないらないよね。メモ化しなくても通してあげるという優しさなのかな？
  • 幅か高さが1のときそれを再分割する必要はない。抽象的には、eval(a) + eval(b) <= eval(a ++ b) (++は何らかの二項演算。ここでは文字列としての連結)だから。
  • ちゃんとコメントも付けて、満足度の高いコードが書けた。
    • 欲を言えば速度がまだ遅いけど、今はそれを気にするフェーズではないから敢えて無視する。バグなく書けたのが嬉しい。

practiceで通ったコード

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

const int MAX_W = 4;
bool visited[MAX_W+1][MAX_W+1][MAX_W+1][MAX_W+1];
int memo[MAX_W+1][MAX_W+1][MAX_W+1][MAX_W+1];

vector<string> board;

struct CutTheNumbers {

	int maximumSum(vector <string> _board) {
		board = _board;
		return rec(0, (int)board.size(), 0, (int)board[0].length());
	}

	//[h1,h2) * [w1, w2) の開区間で考える
	int rec(int h_low, int h_high, int w_low, int w_high){

		//メモ化処理
		if(visited[h_low][h_high][w_low][w_high]){
			return memo[h_low][h_high][w_low][w_high];
		}
		visited[h_low][h_high][w_low][w_high] = true;

		int height = h_high - h_low, width = w_high - w_low;

		//1列or1行になったときは、そのまま和を取るのが最善
		if(height == 1 || width == 1){
			int ret = 0;
			if(height == 1){
				for(int w=w_low; w<w_high; w++){
					ret = ret*10 + (board[h_low][w] - '0');
				}
			}
			else{
				for(int h=h_low; h<h_high; h++){
					ret = ret*10 + (board[h][w_low] - '0');
				}
			}
			return memo[h_low][h_high][w_low][w_high] = ret;
		}

		int ret = 0;

		//縦方向の分割
		for(int mid=h_low+1; mid<h_high; mid++){
			ret = max(ret, rec(h_low, mid, w_low, w_high) + rec(mid, h_high, w_low, w_high));
		}


		//横方向の分割
		for(int mid=w_low+1; mid<w_high; mid++){
			ret = max(ret, rec(h_low, h_high, w_low, mid) + rec(h_low, h_high, mid, w_high));
		}

		return memo[h_low][h_high][w_low][w_high] = ret;
	}
};

後日知人に指摘されて気づいたこと

  • まず、こういう垂直方向か水平方向で再帰的に割る割り方をチョコレート割りと呼ぶらしいことを知った。
    • これが一般に広く敷衍している言葉なのかどうかは知らないけど、イメージはし易い良い表現だと思った。
    • 適切な名前がつくことは考えやすくするためにも重要。
  • で、自分は指摘されるまで勘違いしていたのだけど、この問題はチョコレート割りである必要はないらしい。
  • 実際にテストに通っているから本当は最大和を満足するチョコレート割りが存在するのかもしれないけど、直感ですぐ分かる話でもない。
  • なので、きちんとチョコレート割り以外の分割も考えてやろう。
  • チョコレート割り以外のも考えると、各セルは幅1の長方形に含まれるか高さ1の長方形に含まれるかのどちらかなので、2^16通り調べてやれば良い。
BruteForce解

計算量O( (W*H)*2^(W*H) )。

	int maximumSum(vector <string> board) {
		int H = board.size(), W = board[0].length();
		int ret = 0;

		//意味のある切断を全部列挙する
		for(int bit=0; bit < (1<<(H*W)); bit++){
			vector<string> which = board; //各セルが横成分に含まれるのか縦成分に含まれるのか
			for(int h=0; h<H; h++)for(int w=0; w<W; w++){
				int k = h*W + w;
				which[h][w] = (((bit>>k)&1)?'h':'v');
			}
			ret = max(ret, func(board, which));
		}

		return ret;
	}

	//切断の仕方を与えたときに、和を計算する
	int func(const vector<string>& board, vector<string> which){
		int H = board.size(), W = board[0].length();
		int ret = 0;

		for(int h=0; h<H; h++)for(int w=0; w<W; w++)if(which[h][w] != 'x'){
			int tmp = 0;

			if(which[h][w] == 'h'){ //縦
				for(int i=h; i<H && which[i][w] == 'h'; i++){
					which[i][w] = 'x';
					tmp = 10*tmp + (board[i][w] - '0');
				}
			}
			else if(which[h][w] == 'v'){ //横
				for(int j=w; j<W && which[h][j] == 'v'; j++){
					which[h][j] = 'x';
					tmp = 10*tmp + (board[h][j] - '0');
				}
			}
			ret += tmp;
		}

		return ret;
	}

};

上位陣の回答をまだ見てないので、後で追記する。