Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-10-21SRM485 Div1

SRM485 Div1 250 AfraidOfEven

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

Problem Statement

コーディングフェーズ

何となく、全探索するだけの予感がする。

全部の数字を2倍していって、最初にOKになった等差数列を返す。

計算時間が気になるけど・・・まあ、250だし、対数時間だから多分大丈夫だろう(ちょっと適当でした)

→(多少コーディングに悩んで時間を浪費)

→提出


チャレンジフェーズ

特に突っ込みどころなし


システムテスト

Passed


ソースコード

class AfraidOfEven {
public:
	vector <ll> r;
	vector <int> seq;
	int n;

	bool rec(int d) {
		bool res=false;
		ll nnum=seq[d];
		while(1) {
			r[d]=nnum;
			if(d>1 && r[d]-r[d-1]>r[d-1]-r[d-2]) break;
			if(d<=1 && r[d]>3000000000LL) break;
			if(d<=1 || r[d]-r[d-1]==r[d-1]-r[d-2]) {
				if(d==n-1) return true;
				res=rec(d+1);
				if(res) return true;
			}
			nnum*=2;
		}
		return false;
	}

	vector <int> restoreProgression(vector <int> seq) {
		vector <int> res;
		this->seq=seq;
		n=seq.size();

		r.resize(n);
		rec(0);
		for(int i=0; i<n; i++) res.push_back((int)r[i]);
		return res;
	}
};

SRM485 Div1 500 RectangleAvoidingColoring

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

Problem Statement

コーディングフェーズ

任意の2*2以上の長方形の中身が全て同じ色になることがないようなパターン数を求める問題と理解(←大間違い)

→色々考える

→考える・・・

→・・・

→・・・

→(45分後)

→どうかんがえても無理。解けると思えない。

→というか・・

→よく考えたら50*50の?のみの盤面で、解が明らかに64bitを超える

→え・・?

→問題読み間違ったかっ

→案の定間違えてた。4隅が同じ色にならないようにするパターンを数える問題だったのか。道理で解けないと思った

→終了


チャレンジフェーズ

何もせず。


終了後

さて解くか

→色々試してみると分かるが幅5以上になると、高さは最大4となる。従って、高さより幅が大きい場合は縦と横を入れ替えてやることで、常に幅を4以下として扱うことが可能。(min(幅,高さ)が5以上となる場合は答えは0になる)

→ということで適当にDPする

→自分のとったやり方は、rowを1行ずつ処理していって、黒と白それぞれで、これまで登場したrowに以下のパターンが含まれるかどうか記憶する

{1100,1010,0110,1001,0101,0011}

黒と白それぞれ6パターンしか覚えなくて良いので、50*2^6*2^6で20万くらいの配列で実装できます。

何となく時間内に解けなくもなさそうなレベル。勿体無い。。。


ソースコード

int idtomask[6];
int shift;
ll memo[52][65][65];

class RectangleAvoidingColoring {
public:
	vector <string> b;
	int w, h;

	ll rec(int d, int bmask, int wmask) {
		ll res=0;

		if(d==h) return 1;
		if(memo[d][bmask][wmask]>=0) return memo[d][bmask][wmask];

		for(int i=0; i<(1<<w); i++) {
			bool ok=true;
			for(int j=0; j<w; j++) {
				if(b[d][j]=='B' && !(i&(1<<j))) ok=false;
				if(b[d][j]=='W' && (i&(1<<j))) ok=false;
			}
			if(!ok) continue;
			ok=true;
			int nbmask=bmask;
			for(int j=0; j<shift; j++) {
				if((idtomask[j]&i)!=idtomask[j]) continue;
				nbmask|=(1<<j);
				if(bmask&(1<<j)) ok=false;
			}
			if(!ok) continue;
			ok=true;
			int nwmask=wmask;
			int ii=((1<<w)-1)^i;
			for(int j=0; j<shift; j++) {
				if((idtomask[j]&ii)!=idtomask[j]) continue;
				nwmask|=(1<<j);
				if(wmask&(1<<j)) ok=false;
			}
			if(!ok) continue;
			res+=rec(d+1, nbmask, nwmask);
		}

		memo[d][bmask][wmask]=res;
		return res;
	}

	long long count(vector <string> board) {
		long long res;
		h=board.size(), w=board[0].size();
		idtomask[0]=3; idtomask[1]=5; idtomask[2]=6; idtomask[3]=9; idtomask[4]=10; idtomask[5]=12;

		memset(memo, -1, sizeof(memo));
		if(h<w) {
			for(int i=0; i<w; i++) {
				b.push_back(string());
				for(int j=0; j<h; j++) {
					b[i].push_back(board[j][i]);
				}
			}
			swap(h, w);
		} else b=board;
		if(w>=5) return 0;
		if(w==4) shift=6;
		else if(w==3) shift=3;
		else shift=1;

		if(w==1) {
			int cnt=0;
			for(int i=0; i<h; i++) if(b[i][0]=='?') cnt++;
			return 1LL<<cnt;
		}

		res=rec(0, 0, 0);
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20101021