Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-11-30SRM525 Div1(Practice)

SRM525 Div1 300 DropCoins

| 20:34 | SRM525 Div1 300 DropCoins - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM525 Div1 300 DropCoins - SRM diary(Sigmar) SRM525 Div1 300 DropCoins - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

残す矩形を全探索

矩形の中身にコインが何枚あるか愚直に数えるとO(n^6)で7億くらいになる

といってもある程度枝刈りが入るので何とか間に合うレベルのようである

コインの数はDPで数えると計算量がO(n^4)に落ちるので安心


ソースコード

int dp[32][32];

class DropCoins {
public:
	int getMinimum(vector <string> board, int K) {
		int res;
		int h=board.size(), w=board[0].size();

		memset(dp, 0, sizeof(dp));
		for(int i=1; i<=h; i++) {
			for(int j=1; j<=w; j++) {
				dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
				if(board[i-1][j-1]=='o') dp[i][j]++;
			}
		}

		res=1000000000;

		for(int i=0; i<h; i++) {
			for(int j=i+1; j<=h; j++) {
				int d=h-j;
				for(int k=0; k<w; k++) {
					for(int l=k+1; l<=w; l++) {
						int r=w-l;
						int sum=dp[j][l]-dp[i][l]-dp[j][k]+dp[i][k];
						if(sum!=K) continue;
						int tres=min(i, d)*2+max(i, d)+min(k, r)*2+max(k, r);
						res=min(res, tres);
					}
				}
			}
		}

		if(res>=1000000000) res=-1;
		return res;
	}
};

SRM525 Div1 525 Rumor

| 20:34 | SRM525 Div1 525 Rumor - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM525 Div1 525 Rumor - SRM diary(Sigmar) SRM525 Div1 525 Rumor - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

Aを知ってる人とBを知ってる人を別々に管理すると、状態が2^32になる

どう考えても無理なので、別々に管理しなくても良い方法がないか考える・・・

十分に検討した結果、やはり別々に管理しないと無理。

さて・・

どうしよう。


・・・


待てよ

そもそも一度噂を伝搬した人は、一度に伝搬できる相手全員に伝搬するわけだから、二回以上伝搬する必要がない。

ということは、噂を受け取った次のターンで伝搬してしまえば、そのあとは一切伝搬しなくて良いことになる。

噂が二種類あるので、二種類の噂を同時に受け取ったときだけが問題か

このときに各ウサギがどちらの噂を優先的に伝搬するのか、2^16で全探索すれば良いのではないか。

優先順位が2^16、それぞれにつきシミュレーションが・・

最大伝搬回数16回くらい、16人それぞれで16人へ伝搬するとすると合計で16^3

2^16 * 16^3 = 2^28 ≒ 2億6千万くらい。

内部ループが重そうだし、ちょっと枝刈りが期待できるか微妙なので怪しい。

いや、16人へ伝搬する部分をビットマスク化すれば、計算量を16分の1に減らせる。

これなら計算量は1億以下で余裕ぽい。


書いてみた。

ビットマスクがいっぱい出てきて泣きそうになった。

一応一発で通った。本番でもこのくらいのパフォーマンスを出したい。。。


後でピョートルの成績を見たら470点台とかでどういう頭の回転してるんだろうって思った

コーディングが余りにも早過ぎる。。。


ソースコード

class Rumor {
public:
	vector <int> prop;
	int n;
	int allmask;

	//priamask -> Aを優先的に伝搬するウサギ
	//amask -> Aを知っているウサギ
	//immedamask -> 次のターンでAを伝搬するウサギ
	//delayamask -> 次の次のターンでAを伝搬するウサギ
	//Bについても同様
	int go(int priamask, int pribmask, int amask, int bmask, int immedamask, int delayamask, int immedbmask, int delaybmask) {
		if(amask==allmask && bmask==allmask) return 0;

		int namask, nbmask, nimmedamask, ndelayamask, nimmedbmask, ndelaybmask;
		namask=amask; nbmask=bmask;
		nimmedamask=delayamask; ndelayamask=0;
		nimmedbmask=delaybmask; ndelaybmask=0;
		for(int i=0; i<n; i++) {
			if(immedamask&(1<<i)) namask|=prop[i];
			if(immedbmask&(1<<i)) nbmask|=prop[i];
		}
		int diffamask=amask^namask;
		int diffbmask=bmask^nbmask;
		if(diffamask==0 && diffbmask==0) return 1000000000;

		int diffabmask=diffamask&diffbmask;
		diffamask^=diffabmask;
		diffbmask^=diffabmask;
		nimmedamask|=diffamask;
		nimmedamask|=priamask&diffabmask;
		nimmedbmask|=diffbmask;
		nimmedbmask|=pribmask&diffabmask;
		ndelayamask|=pribmask&diffabmask;
		ndelaybmask|=priamask&diffabmask;
		int res=go(priamask, pribmask, namask, nbmask, nimmedamask, ndelayamask, nimmedbmask, ndelaybmask)+1;
		return res;
	}

	int getMinimum(string know, vector <string> graph) {
		int res;
		n=know.size();
		prop.clear();
		for(int i=0; i<n; i++) {
			int e=0;
			for(int j=0; j<n; j++) {
				if(graph[i][j]=='Y') e|=(1<<j);
			}
			prop.push_back(e);
		}

		int initmask=0;
		for(int i=0; i<n; i++) if(know[i]=='Y') initmask|=(1<<i);
		allmask=(1<<n)-1;

		res=1000000000;
		for(int priamask=0; priamask<(1<<n); priamask++) {
			int pribmask=allmask^priamask;
			res=min(res, go(priamask, pribmask, initmask, initmask, priamask&initmask, pribmask&initmask, pribmask&initmask, priamask&initmask));
		}

		if(res>=1000000000) res=-1;
		return res;
	}
};

laycrslaycrs2011/11/30 22:01((525pt, 自分は,最大ターンは約16だけど,各人2回しか情報を伝搬しないので16^2 * 2^16と見積もってビット使わず突撃しました.

SigmarSigmar2011/11/30 22:57確かにそうですね!
3重目のループに入る回数は16*2でたかだか32回のような気がします。そうすると、おっしゃるとおりシミュレーションは16^2のオーダーなので、ビットを使わなくても計算量は問題なさそうですね。
コメントありがとうございました。

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