Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-05-03SRM505 Div1

  • 300:Opened, 500:Opened, score:0.0, rank:306, rating:2050(-122)
  • 向いてない問題セットだった。Easy通ったのが300人未満とか全体的にもあまりに難易度高すぎでは?

SRM505 Div1 300 RectangleArea

| 00:18 | SRM505 Div1 300 RectangleArea - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM505 Div1 300 RectangleArea - SRM diary(Sigmar) SRM505 Div1 300 RectangleArea - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

うむ意味わからん

サンプル0から類推するに、要するにある四角形の4隅のうち3隅が分かれば残りの1隅の面積分かるよと言いたいらしい

例えば、{"YNNY", "YNNN"}とかあったら、右下のNがYになると思えばいい

で・・・?

GreedyにまだYになってないNをYにするとか?で良い訳ないよなあ・・

・・・

・・・

と思ったが、よく考えるとそれでいいような気がする

"YN", "NY"みたいなのがあれば、どちらのNをYにしても同じで可換ぽい

書き始める

途中でなんかやっぱり間違ってる気がしてきた

30分経ってるしハマりそうだから500も見ておこう→数論ですぐに解法が思いつきそうもない感じだったのですぐ戻ってきた

やっぱりさっきの解法は怪しくて別の方法で解けそうな気がする

例えば"YYNN", "YYNN"とかみたいに同じ行があれば併合して一つの行にできるのではないか

それから"YYNN", "NNYY"みたいにYが一つも重複しない行は1つNをYに変えればやはり併合できるのではないか

とか色々考えていたらコーディングフェーズが終わってしまった


後で

まず1つ目の解法ですが実際GreedyにNをYに変えていくだけで良かったらしい

とりあえず書いて出しとけばよかった・・・・・・・・・・


2つ目の解法ですがやはりこちらでも解けそう

"YYNN", "NYYN"みたいに2つの行で1つでも同じ列にYがある場合は、必ず"YYYN", "YYYN"というようにYのパターンをORできる

行と列を入れ替えても同じ

ということでどんどん併合していって、最終的に各行と列にYはたかだか1個だけ残る

Nのみしかない列や行は併合できないので残す

すると{"YNNNN", "NYNNN", "NNNNN"}みたいな感じになる

Nのみの行と列はそれぞれYを1個ずつ追加しないといけないので解に行数と列数を加える(上の例では行1+列3)

Yを含む行と列は、行数(例では2)からマイナス1しただけ併合が必要なのでそれを加える

ちなみにYがひとつもない場合は行数+列数-1が答えになる

以上をまとめるとソースは以下のようになる


あとチャレンジフェーズ見た感じではすごく短い解法の人もいたので他にも何かありそうです。


ソースコード

解法1

class RectangleArea {
public:
	void rec(int i, int j, int n, int m, vector <string> &known) {
		for(int k=0; k<n; k++) {
			for(int l=0; l<m; l++) {
				if(known[k][l]=='N' && known[k][j]=='Y' && known[i][l]=='Y') {
					known[k][l]='Y';
					rec(k, l, n, m, known);
				}
				if(known[k][l]=='Y' && known[k][j]=='N' && known[i][l]=='Y') {
					known[k][j]='Y';
					rec(k, j, n, m, known);
				}
				if(known[k][l]=='Y' && known[k][j]=='Y' && known[i][l]=='N') {
					known[i][l]='Y';
					rec(i, l, n, m, known);
				}
			}
		}
	}

	int minimumQueries(vector <string> known) {
		int res=0;

		int n=known.size(), m=known[0].size();
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(known[i][j]=='Y') continue;
				for(int k=0; k<n; k++) {
					for(int l=0; l<m; l++) {
						if(k==i || l==j) continue;
						if(known[k][l]=='Y' && known[k][j]=='Y' && known[i][l]=='Y') {
							known[i][j]='Y';
							rec(i, j, n, m, known);
						}
					}
				}
			}
		}

		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(known[i][j]=='N') {
					res++;
					known[i][j]='Y';
					rec(i, j, n, m, known);
				}
			}
		}

		return res;
	}
};

解法2

class RectangleArea {
public:
	bool unionk(vector <string> &known) {
		bool res=false;
		int n=known.size(), m=known[0].size();
		for(int i=0; i<n; i++) {
			for(int k=i+1; k<n; k++) {
				for(int j=0; j<m; j++) {
					if(known[i][j]=='Y' && known[k][j]=='Y') {
						for(int l=0; l<m; l++) if(known[k][l]=='Y') known[i][l]='Y';
						known.erase(known.begin()+k);
						n--;
						k--;
						res=true;
						break;
					}
				}
			}
		}

		return res;
	}

	void reversek(vector <string> &known) {
		int n=known.size(), m=known[0].size();
		vector <string> res(m, string(n, 'N'));
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(known[i][j]=='Y') res[j][i]='Y';
			}
		}
		known=res;
	}

	int minimumQueries(vector <string> known) {
		int res=0;

		bool changed=true;
		while(changed) {
			changed=false;
			changed|=unionk(known);
			reversek(known);
			changed|=unionk(known);
			reversek(known);
		}

		int n=known.size(), m=known[0].size();
		int cnt=0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(known[i][j]=='Y') {
					cnt++;
					break;
				}
			}
		}

		res=cnt+(n-cnt)+(m-cnt)-1;
		return res;
	}
};

ゲスト



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