Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-03-02SRM533 Div1

SRM533 Div1 250 CasketOfStar

| 17:22 | SRM533 Div1 250 CasketOfStar - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM533 Div1 250 CasketOfStar - SRM diary(Sigmar) SRM533 Div1 250 CasketOfStar - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

最後の状態から逆に考えれば、範囲を指定したDPができる

書いた

バグっててなかなか治らなかった

半開区間にしたのが失敗だった。もっと考えれば良かった。


ソースコード

int memo[52][52];

class CasketOfStar {
public:
	int n;
	vector <int> weight;

	int rec(int b, int e) {
		int res=0;
		if(e==b+2) return 0;
		if(memo[b][e]>=0) return memo[b][e];

		for(int i=b+1; i<e-1; i++) {
			res=max(res, rec(b, i+1)+rec(i, e));
		}
		res+=weight[b]*weight[e-1];
		memo[b][e]=res;
		return res;
	}

	int maxEnergy(vector <int> weight_) {
		int res;
		weight=weight_;
		n=weight.size();

		memset(memo, -1, sizeof(memo));
		res=rec(0, n);
		return res;
	}
};

SRM533 Div1 500 MagicBoard

| 17:22 | SRM533 Div1 500 MagicBoard - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM533 Div1 500 MagicBoard - SRM diary(Sigmar) SRM533 Div1 500 MagicBoard - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

何か場合分け解法しか思いつかない

場合分け解法はとても危ない。やりたくない。

・・・

やっぱり思いつかないのでしょうがないので場合分け解法で書く

要素が奇数個の行数と奇数個の列数で場合分けする

一筆書きと似ていて、奇数個の行数は最大1個までが限界

奇数個の列数は2個まで

チェックする必要はないのだが、奇数個の行が奇数個なら奇数個の列も奇数個になる

あとは連結をチェックして終了


こんなんでいいのか・・・

(通りましたが・・)


ソースコード

class MagicBoard {
public:
	string ableToUnlock(vector <string> board) {
		string res;
		int n=board.size(), m=board[0].size();
		int sr=-1, sc=-1;

		int roddcnt=0;
		for(int i=0; i<n; i++) {
			int cnt=0;
			for(int j=0; j<m; j++) {
				if(board[i][j]=='#') {
					cnt++;
					if(sr==-1) { sr=i; sc=j; }
				}
			}
			if(cnt%2==1) roddcnt++;
		}
		if(roddcnt>1) return "NO";

		int coddcnt=0;
		for(int i=0; i<m; i++) {
			int cnt=0;
			for(int j=0; j<n; j++) {
				if(board[j][i]=='#') cnt++;
			}
			if(cnt%2==1) coddcnt++;
		}
		if(coddcnt>2) return "NO";
		
		if(roddcnt==1) {
			if(coddcnt!=1) return "NO";
		} else {
			if(coddcnt!=0 && coddcnt!=2) return "NO";
		}

		queue <int> q;
		q.push(sr*m+sc);
		int vis[52][52]={0};
		vis[sr][sc]=1;
		while(!q.empty()) {
			int qt=q.front(); q.pop();
			int cr=qt/m, cc=qt%m;
			for(int i=0; i<n; i++) {
				if(board[i][cc]!='#') continue;
				if(vis[i][cc]) continue;
				vis[i][cc]=1;
				q.push(i*m+cc);
			}
			for(int i=0; i<m; i++) {
				if(board[cr][i]!='#') continue;
				if(vis[cr][i]) continue;
				vis[cr][i]=1;
				q.push(cr*m+i);
			}
		}

		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(board[i][j]=='#' && !vis[i][j]) return "NO";
			}
		}
		
		return "YES";
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120302