Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-05-04SRM505 Div1(復習)

SRM505 Div1 500 SetMultiples

| 07:41 | SRM505 Div1 500 SetMultiples - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM505 Div1 500 SetMultiples - SRM diary(Sigmar) SRM505 Div1 500 SetMultiples - SRM diary(Sigmar) のブックマークコメント

Problem Statement

後で

まずA-B区間とC-D区間を分けて考えると、k=2だけ考えれば良い

(B/2以下の数は2倍するとB以下である。また、2倍してもB/2以下の数は更に2倍すればいつかはB/2~Bの区間に入る。逆にB/2よ

り大きい数は2倍するとBを超えるため必ず残す必要がある。)

なのでAはmax(A, B/2+1)、Cはmax(C, D/2+1)とする

あとは、A-B区間のうちC-D区間の約数になっているものを減算するだけである

ここでA-B区間の数を1つ1つイテレートなどすると明らかにTLEとなるため、kをイテレートすることにする

まず最初にk1=D/B, k2=(C-1)/A+1とすると、k1はBがD以下となる最大のkであり、k2はAがC以上となる最小のkである

この時点でk2<=k1だとすると、A-Bの全区間がC-Dに入ることは明白である

続いてk1<k2の場合は、k2をD/Aに置き換えて、kをk1<=k<=k2の区間でイテレートすれば良さそうである

ここであるkのときに、C-D区間に入るA-Bの最大値をhi、最小値-1をloと置く

そうすると、hi-loが必要ない数字の数ということになる

また、次のkはhiがlo以下の最大の値となるように選べば重複が発生しないため単純に解から減じていくことができる

ということで後はコーディングするだけなのであるがminとかmaxとかいっぱい出てきて非常に間違えやすい

実際プラクティスで2回もWAを出した。考え方だけでなくコーナーケースのケアもとても難しい。。。

どうも上位の人の解法を見ると別の書き方をしている人もいるのでもう少し間違えにくい解き方もありそうではある。


ソースコード

class SetMultiples {
public:
	long long smallestSubset(long long A, long long B, long long C, long long D) {
		long long res=0;

		A=max(A, B/2+1);
		C=max(C, D/2+1);
		ll k1=D/B, k2=(C-1)/A+1;
		res=D-C+1;
		if(k2<=k1) return res;

		k2=D/A;
		ll k=k1;
		ll hi=B;
		res+=B-A+1;
		while(k<=k2) {
			ll lo=(C-1)/k;
			res-=max(hi-max(A-1, lo), 0LL);
			k=max(k+1, D/lo);
			hi=min(lo, D/k);
		}

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

2011-05-03SRM505 Div1

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