Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-11-30SRM525 Div1(Practice)

SRM525 Div1 300 DropCoins

| 20:34 | SRM525 Div1 300 DropCoins - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM525 Div1 300 DropCoins - SRM diary(Sigmar) SRM525 Div1 300 DropCoins - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

残す矩形を全探索

矩形の中身にコインが何枚あるか愚直に数えるとO(n^6)で7億くらいになる

といってもある程度枝刈りが入るので何とか間に合うレベルのようである

コインの数はDPで数えると計算量がO(n^4)に落ちるので安心


ソースコード

int dp[32][32];

class DropCoins {
public:
	int getMinimum(vector <string> board, int K) {
		int res;
		int h=board.size(), w=board[0].size();

		memset(dp, 0, sizeof(dp));
		for(int i=1; i<=h; i++) {
			for(int j=1; j<=w; j++) {
				dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
				if(board[i-1][j-1]=='o') dp[i][j]++;
			}
		}

		res=1000000000;

		for(int i=0; i<h; i++) {
			for(int j=i+1; j<=h; j++) {
				int d=h-j;
				for(int k=0; k<w; k++) {
					for(int l=k+1; l<=w; l++) {
						int r=w-l;
						int sum=dp[j][l]-dp[i][l]-dp[j][k]+dp[i][k];
						if(sum!=K) continue;
						int tres=min(i, d)*2+max(i, d)+min(k, r)*2+max(k, r);
						res=min(res, tres);
					}
				}
			}
		}

		if(res>=1000000000) res=-1;
		return res;
	}
};

laycrslaycrs2011/11/30 22:01((525pt, 自分は,最大ターンは約16だけど,各人2回しか情報を伝搬しないので16^2 * 2^16と見積もってビット使わず突撃しました.

SigmarSigmar2011/11/30 22:57確かにそうですね!
3重目のループに入る回数は16*2でたかだか32回のような気がします。そうすると、おっしゃるとおりシミュレーションは16^2のオーダーなので、ビットを使わなくても計算量は問題なさそうですね。
コメントありがとうございました。

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111130