Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-05-22Google Code Jam 2010 Round 1A

Google Code Jam 2010 Round 1A A Rotate

| 21:50 | Google Code Jam 2010 Round 1A A Rotate - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 1A A Rotate - SRM diary(Sigmar) Google Code Jam 2010 Round 1A A Rotate - SRM diary(Sigmar) のブックマークコメント

Problem Statement

Cが終わったので最も簡単と思われるAを解きました。見た感じ、シミュレーションするだけのようなので、何も考えずシミュレーションしました。90度回転後の片寄せのところでバグが出て、おかしな答えが出ていたので修正に30分くらい費やしてしまいました。

さらに、サンプルは答えが合ったのですが、smallでWA。GCJでWAすると、どのケースで間違ったのか分からないため非常に解析に苦労します。手動で答えを数ケース計算して、間違ってるところがすぐに見つかったので良かったですが・・・。結局if文の条件中で括弧付け忘れがあり、計算の優先順位が間違って適用されていたことが原因でした。こういうのに気付かず書いてしまうと、致命的なのに発見しづらいので何とかならないでしょうか・・・。

バグ取りやら何やらで結局40分くらいかかってしまいました。さらに、Largeの解を提出しようとしたらブラウザがフリーズ・・・。なんとか8分以内に復旧したので何とかなりましたが、今日はどうもついていないです。

Aを出し終えた頃には残り10分だったので、Bはとりかかりませんでした。見た感じBはDPぽいですね。解説にもDPと書いてありました。

何とかAもSmall、Large両方通せたので、最終的には64点で305位、Round1は通過しました。次は、かなり厳しくなりそうです。。。

以下、Aのソースです。Inputファイルの解析は省略です。solve関数が本体です。


class GCJ {
public:
	bool ifw(vector <string> vs, int N, int K, int r, int c, char C) {
		int dr[4]={1,1,0,1}, dc[4]={0,1,1,-1}, nr, nc;
		bool flag;

		if(vs[r][c]!=C) return false;
		for(int i=0; i<4; i++) {
			nr=r; nc=c;
			flag=true;
			for(int j=1; j<K; j++) {
				nr+=dr[i]; nc+=dc[i];
				if(nr<0 || nr>=N || nc<0 || nc>=N || vs[nr][nc]!=C) {
					flag=false;
					break;
				}
			}
			if(flag) return true;
		}
		return false;
	}

	string solve(int N, int K, vector <string> vs) {
		string result;
		bool b=false, r=false;
		
		//ボードの左右を反転して左寄せする
		for(int i=0; i<N; i++) {
			reverse(vs[i].begin(), vs[i].end());
		}
		for(int i=0; i<N; i++) {
			for(int j=1; j<N; j++) {
				if((vs[i][j]=='R' || vs[i][j]=='B') && vs[i][j-1]=='.') {
					int idx=j-1;
					while(idx>0) {
						if(vs[i][idx-1]=='.') idx--;
						else break;
					}
					swap(vs[i][idx], vs[i][j]);
				}
			}
		}

		//Red、Blueのどちらか勝つか判定する
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(ifw(vs, N, K, i, j, 'B')) b=true;
				if(ifw(vs, N, K, i, j, 'R')) r=true;
			}
		}

		if(r && b) result="Both";
		else if(r && !b) result="Red";
		else if(!r && b) result="Blue";
		else result="Neither";

		return result;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100522