Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-10-13SRM521 Div1

SRM521 Div1 250 MissingParentheses

| 00:43 | SRM521 Div1 250 MissingParentheses - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM521 Div1 250 MissingParentheses - SRM diary(Sigmar) SRM521 Div1 250 MissingParentheses - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

何か左括弧と右括弧の数の差を取ればいいような気がするが・・

絶対反例ありそう。

・・・

あった。")("←こんなやつ。

えーと・・・左から順番に見て行って、閉じられてない左括弧の数を覚えておけば良いかな

で、閉じられてない左括弧数がマイナスになると、左端に左括弧が必要だから解を+1して左括弧数を0にする。

書けた。

サンプル合った。

提出。


ついでに左括弧と右括弧の数の差を取るプログラムを書いてみる。

こちらもサンプルは全部通る。

反例がチャレンジで使えることが分かった。チャレンジ祭りになりそう。


チャレンジフェーズ

分かりやすいやつは一瞬で誰かに落とされてしまった。

でも2人おかしい人が残っていたので+100。1ミスして-25。儲かった。


ソースコード

class MissingParentheses {
public:
	int countCorrections(string par) {
		int res=0;

		int n=par.size();

		int l=0;
		for(int i=0; i<n; i++) {
			if(par[i]=='(') l++;
			else {
				if(l<=0) res++;
				else l--;
			}
		}
		res+=abs(l);//absである必要は全くない
		return res;
	}
};

SRM521 Div1 500 RangeSquaredSubsets

| 00:43 | SRM521 Div1 500 RangeSquaredSubsets - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM521 Div1 500 RangeSquaredSubsets - SRM diary(Sigmar) SRM521 Div1 500 RangeSquaredSubsets - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

これは・・・いくら何でも問題文が意味不明すぎ

if and only ifってあるけど、ifのほうが成り立つとするなら正方形内の全ての点がPに含まれないといけないんだけど・・・そんな点って無限に存在するんですが・・・

しかも正方形に含まれるというのが、境界線にあるもののみのようにも読み取れるので更に良くない

何とかサンプルから類推すると、与えられたセット内の点のうち、あるサブセットをPとして、P以外のセット内の点が正方形に入ってはいけないということらしい

(一応後でメッセージで補足があったので無限に存在しないというのは分かるようになったようだが・・・)

ともかく題意を理解するのに10分以上かかった。解いた人が少ない原因の一つはこの意味不明な問題文だろう・・・


解法自体はとりあえず登場する全てのx座標とy座標で格子を作って、それで点集合を区切るのが良さそうである

要素数は40だから、セットの数は最大でも40^4/4くらいで64万程度。

重複するものを除くためにstd::setを利用したとしても十分に間に合うと思われる。


適当に書いた。

サンプルの最後が合わない。答えより1多い。

空集合を除くのを忘れていた。。。

修正。サンプルあった。

コーナーケースはないだろうか。ないようだ。

最大ケースで0.1秒くらい。楽勝っぽい。

提出。


ソースコード

class RangeSquaredSubsets {
public:
	long long countSubsets(int nlow, int nhigh, vector <int> x, vector <int> y) {
		long long res;
		int n=x.size();

		vector <int> xx=x, yy=y;
		xx.push_back(-300000000);
		xx.push_back(300000000);
		sort(xx.begin(), xx.end());
		xx.erase(unique(xx.begin(), xx.end()), xx.end());
		yy.push_back(-300000000);
		yy.push_back(300000000);
		sort(yy.begin(), yy.end());
		yy.erase(unique(yy.begin(), yy.end()), yy.end());

		set <vector <int> > ress;

		int xsz=xx.size(), ysz=yy.size();
		for(int i=1; i<xsz-1; i++) {
			for(int j=i; j<xsz-1; j++) {
				for(int k=1; k<ysz-1; k++) {
					for(int l=k; l<ysz-1; l++) {
						int xlo=xx[i], xhi=xx[j];
						int ylo=yy[k], yhi=yy[l];
						int xllo=xx[i-1], xlhi=xx[j+1];
						int yllo=yy[k-1], ylhi=yy[l+1];
						int minside=max(xhi-xlo, yhi-ylo);
						int maxside=min(xlhi-xllo, ylhi-yllo);
						if(minside>=maxside) continue;
						if(nhigh<minside) continue;
						if(nlow>=maxside) continue;
						vector <int> pts;
						for(int m=0; m<n; m++) {
							if(x[m]>=xlo && x[m]<=xhi && y[m]>=ylo && y[m]<=yhi) pts.push_back(m);
						}
						if(pts.empty()) continue;
						ress.insert(pts);
					}
				}
			}
		}

		res=ress.size();
		return res;
	}
};

SRM521 Div1 1000 Chimney

| 00:43 | SRM521 Div1 1000 Chimney - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM521 Div1 1000 Chimney - SRM diary(Sigmar) SRM521 Div1 1000 Chimney - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

珍しく時間が余っているから1000でも読んでおこうかな

見た感じどうも適当に状態を定義して行列の累乗をすれば良いように見える。

あるレイヤーがチムニー4個未満で構成されるようなパターンがどの程度あるのか考えてみたが、かなり少ないようだ。

1つのチムニーの下に2つのチムニーがあることを考慮すると、最大でも4個未満のレイヤーは、下から3個、2個、1個の3段にしかならない。

他にも4個未満がないもの(初期状態と同じ)とか、1個だけとか、2個だけとか、2個、1個の2段とか、色々考えると10通りくらいか。

(9通りにできなくもなさそうだったけど)

ある状態から別の状態への遷移は1個のチムニーをどのように載せるか考えるだけだから、あんまり難しくない。

行列を作ってみた。

まあ、こんな簡単に答え合うわけないよね。と思ったらサンプルが一発で全部通ってしまった。

残り2分くらいだから記念に提出しとこう。Hardの問題出したこと無いし。

で、結局システムテストも通ってしまった。うーむ。500より簡単じゃないの。。。これ。。。


ソースコード

const int MOD=1000000007;

//MOD上のベクトルクラス
class VectorGF {
private:
	vector <int> data;
	int vsize;
	int MOD;
public:
	VectorGF() { vsize=0; MOD=0; }
	VectorGF(int _vsize, int _MOD) { data.assign(_vsize, 0); vsize=_vsize; MOD=_MOD; }
	int size() const { return vsize; }
	void clear() { data.clear(); }
	void resize(int _vsize) { data.resize(_vsize); vsize=_vsize; }
	int mod() const { return MOD; }
	int mod(int _MOD) { MOD=_MOD; return MOD; }
	const int& operator[](const int idx) const { return data[idx]; }
	int& operator[](const int idx) { return data[idx]; }
	VectorGF operator*(const int mul) const {
		VectorGF res(vsize, MOD);
		for(int i=0; i<vsize; i++) res[i]=(ll)data[i]*mul%MOD;
		return res;
	}
};
VectorGF operator*(const int mul, const VectorGF& v) {
	VectorGF res(v.size(), v.mod());
	for(int i=0; i<(int)v.size(); i++) res[i]=(ll)v[i]*mul%v.mod();
	return res;
}

//MOD上の行列クラス
class MatrixGF {
private:
	vector <VectorGF> data;
	int rows, cols;
	int MOD;
public:
	MatrixGF() { rows=0; cols=0; MOD=0; }
	MatrixGF(int _rows, int _MOD) {
		data.assign(_rows, VectorGF(_rows, _MOD));
		for(int i=0; i<_rows; i++) data[i][i]=1;
		rows=_rows; cols=_rows; MOD=_MOD;
	}
	MatrixGF(int _rows, int _cols, int _MOD) { data.assign(_rows, VectorGF(_cols, _MOD)); rows=_rows; cols=_cols; MOD=_MOD; }
	int size1() const { return rows; }
	int size2() const { return cols; }
	void clear() { data.clear(); }
	void resize(int _rows, int _cols) {
		data.resize(_rows);
		for(int i=0; i<_rows; i++) data[i].resize(_cols);
		rows=_rows; cols=_cols;
	}
	int mod() const { return MOD; }
	int mod(int _MOD) { MOD=_MOD; return MOD; }
	const VectorGF& operator[](const int idx) const { return data[idx]; }
	VectorGF& operator[](const int idx) { return data[idx]; }
	MatrixGF operator+(const MatrixGF& b) const {
		MatrixGF res(rows, cols, MOD);
		for(int i=0; i<rows; i++) for(int j=0; j<cols; j++) res[i][j]=((ll)data[i][j]+b[i][j])%MOD;
		return res;
	}
	MatrixGF operator-(const MatrixGF& b) const {
		MatrixGF res(rows, cols, MOD);
		for(int i=0; i<rows; i++) for(int j=0; j<cols; j++) res[i][j]=((ll)data[i][j]-b[i][j])%MOD;
		return res;
	}
	MatrixGF operator*(const MatrixGF& b) const {
		if(cols!=(int)b.size1()) return MatrixGF(0, 0, MOD);
		MatrixGF res(rows, b.size2(), MOD);
		for(int i=0; i<rows; i++) for(int j=0; j<cols; j++) {
			ll tmp=0;
			for(int k=0; k<cols; k++) tmp+=(ll)data[i][k]*b[k][j]%MOD;
			res[i][j]=(int)(tmp%MOD);
		}
		return res;
	}
	MatrixGF operator*(const int mul) const {
		MatrixGF res(rows, cols, MOD);
		for(int i=0; i<rows; i++) for(int j=0; j<cols; j++) res[i][j]=((ll)data[i][j]*mul)%MOD;
		return res;
	}
	VectorGF operator*(const VectorGF& v) const {
		if(cols!=(int)v.size()) return VectorGF(0, MOD);
		VectorGF res(rows, MOD);
		for(int i=0; i<rows; i++) {
			ll tmp=0;
			for(int k=0; k<cols; k++) tmp+=(ll)data[i][k]*v[k]%MOD;
			res[i]=(int)(tmp%MOD);
		}
		return res;
	}
	MatrixGF pow(ll n) {
		if(rows!=cols) return MatrixGF(0, 0, MOD);
		if(n==0) return MatrixGF(rows, MOD);
		if(n%2==0) {
			MatrixGF tmp=this->pow(n/2);
			return tmp*tmp;
		} else {
			return (*this)*(this->pow(n-1));
		}
	}
	//E+A+A^2+...+A^n
	MatrixGF geometric_progression(ll n) {
		if(rows!=cols) return MatrixGF(0, 0, MOD);
		if(n==0) return MatrixGF(rows, MOD);
		if(n%2==1) return (this->pow(n/2+1)+MatrixGF(rows, MOD))*this->geometric_progression(n/2);
		else return this->pow(n)+this->geometric_progression(n-1);
	}
};
MatrixGF operator*(const int mul, const MatrixGF& m) {
	MatrixGF res(m.size1(), m.size2(), m.mod());
	for(int i=0; i<(int)m.size1(); i++) for(int j=0; j<(int)m.size2(); j++) res[i][j]=(ll)m[i][j]*mul%m.mod();
	return res;
}

class Chimney {
public:
	int countWays(long long n) {
		int res;

		//状態を10個に分ける。11個目は定数項で作ったけど使わなかった。状態6と7も同一視して良かった。
		//状態の表現方法として、4個未満のレイヤーが下からチムニー何個で構成されるかで表す
		//状態0:0のパターン(=初期状態)
		//状態1:1-0のパターン
		//状態2:2-0のパターン(隣接しない)
		//状態3:2-0のパターン(隣接する)
		//状態4:2-1-0のパターン
		//状態5:3-0のパターン
		//状態6:3-1-0のパターンその1
		//状態7:3-1-0のパターンその2
		//状態8:3-2-0のパターン
		//状態9:3-2-1-0のパターン

		MatrixGF A(11, MOD);
		for(int i=0; i<11; i++) for(int j=0; j<11; j++) A[i][j]=0;
		A[1][0]=4;
		A[2][1]=1; A[3][1]=2;
		A[5][2]=2;
		A[5][3]=2; A[4][3]=1;
		A[6][4]=1; A[7][4]=1;
		A[0][5]=1; A[6][5]=1; A[7][5]=1;
		A[1][6]=1; A[8][6]=1;
		A[1][7]=1; A[8][7]=1;
		A[3][8]=1; A[9][8]=1;
		A[4][9]=1;
		A[10][10]=1;

		VectorGF V(11, MOD);
		for(int i=0; i<11; i++) V[i]=0;
		V[0]=V[10]=1;

		A=A.pow(n*4);//1レイヤーにつきチムニー4個なので4倍する
		V=A*V;
		res=V[0]%MOD;
		return res;
	}
};

prosho007prosho0072011/10/14 13:33赤おめでとうございます!

kojingharangkojingharang2011/10/14 17:46すごいっす、おめでとうございます~

SigmarSigmar2011/10/14 21:54prosho007さん、kojingharangさん、ありがとうございます!
何とかこの色を維持できるよう頑張ります。

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