Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-01-28SRM495 Div1

SRM495 Div1 275 ColorfulCards

| 01:44 | SRM495 Div1 275 ColorfulCards - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM495 Div1 275 ColorfulCards - SRM diary(Sigmar) SRM495 Div1 275 ColorfulCards - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

全てが一意に定まらなければ{-1}を返すと勘違いしDPで解けそうな気がしたので進める

意外とうまく解けなくてはまる

20分くらいで何となくできた気がしたがサンプル合わない

というか全然勘違いしてる!!!サンプルの解って-1がいっぱいある何これ

読み直すと一意に定まらない部分だけ-1を返すことに気づく

頑張ってそのままDPを修正して何とかならないか・・

20分後全く答えが合わないのであきらめて500へ


後で

冷静になって考えれば皆さんがやっている両サイドからの挟み撃ち的な解が素直で当然思いつくべき解だと思う

最初にDPに行った時点で完全にループに陥った・・

まあDPでもちゃんと書けば解けるのだが。焦ってばかりでそんな精神状態を保てていない。。。

以下書きたかった内容のDPのソース

//エラトステネスの篩
vector <bool> cpn(int n) {
	vector <bool> vn(max(2, n+1), true);

	vn[0]=vn[1]=false;
	for(int i=2; i*i<=n; i++) {
		if(!vn[i]) continue;
		for(int j=i*i; j<=n; j+=i) {
			vn[j]=false;
		}
	}
	
	return vn;
}

class ColorfulCards {
public:
	vector <int> theCards(int N, string col) {
		vector <int> res(col.size(), 0);

		vector <bool> vn=cpn(1001);

		int dp[52][1010];
		int dp2[52][1010];
		memset(dp, 0, sizeof(dp));
		memset(dp2, 0, sizeof(dp2));
		dp[0][1]=1;
		for(int i=1; i<=N; i++) {
			for(int j=0; j<=min(i, (int)col.size()-1); j++) {
				if(dp[j][i]==0) continue;
				if(vn[i]==(col[j]=='R')) {
					dp[j+1][i+1]=1;
					dp2[j][i]=1;
				}
				dp[j][i+1]=1;
			}
		}

		for(int j=0; j<(int)col.size(); j++) dp[j][N+1]=0;
		for(int j=col.size()-1; j>=0; j--) {
			for(int i=N; i>=1; i--) {
				if((dp[j+1][i+1]==0 || vn[i]!=(col[j]=='R')) && dp[j][i+1]==0) {
					dp[j][i]=0;
					dp2[j][i]=0;
				}
			}
		}

		for(int j=0; j<(int)col.size(); j++) {
			for(int i=1; i<=N; i++) {
				if(res[j]==0) {
					if(dp2[j][i]) res[j]=i;
				} else if(res[j]>0) {
					if(dp2[j][i]) res[j]=-1;
				}
			}
		}

		return res;
	}
};
//この書き方の難易度が高いところ
//・カード色と数を当てはめた場所を記憶するためdp2を導入する必要がある
//・dp[col.size()][N+1]に辿りつけないノードを後ろから初期化していく必要がある
//・そのために最初にdp[0~col.size()-1][N+1]を初期化する必要がある
//以上は全てかなり分かりにくいポイントであり短時間で整理して書くのは厳しい
//dp[col.size()][N+1]に辿りつけないノードの初期化はもう少し効率を悪くすれば簡単に書けそうだが・・・

SRM495 Div1 500 CarrotBoxes

| 01:44 | SRM495 Div1 500 CarrotBoxes - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM495 Div1 500 CarrotBoxes - SRM diary(Sigmar) SRM495 Div1 500 CarrotBoxes - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

Yを人参が入っている箱と勘違いする

色々悩む

箱を開けると1/nの確率で空箱なので、これを繰り返すと(乗算で)確率が求まるのか?

適当に書く

サンプル合わない

今更だがどうしても矛盾が発生する気がする。空箱が3だったときに1を開けて3がYだったらどうなるんだ

もう一度よく読むとYのところは人参箱決定ではなく、人参箱か空箱かが分かると書いてある

・・・終わった・・・

というか最初におかしいって気づけよ・・

時間切れ


後で

さて・・解くか・・

  • サンプル3の解析とかシミュレーション計算ですぐ分かるが、n個の箱の状態が全て分かるまで空箱が特定できない場合のみを考えても問題ない(そうでない場合も確率は結局同じになる)
  • その場合に、空箱の可能性がある箱を開けた数をkとすると、答えは(n-k)/nになる(k/nの確率で空箱を開けてしまうから)
  • 最後の1個は開けなくても全状態が把握可能(n-1個分かれば当然残りの1個の状態も分かるから)
  • 1個は開けなくていい箱があるが、これは50通りしかないので単純に全探索すればいい
  • informationを有向グラフと見ると、直感的に言えば入力辺がない箱は全て開けなければならないのは明らかだが、これは必要であって十分でない、なぜならループがある場合があるから
  • 入力辺がない箱を全て開けたとき、残るのはループを持つノードのみである。ということはあとは残ったのをGreedyに適当に開けていけば良いのかというと、これも真ではない
  • ループ構造からループ構造への一方向性がある場合がある。例えば、、A->B、B->A、C->A、C->D、D->Cの4ノード5エッジを考えると、AかBを開けると追加でCかDを開けなければならないのに対し、CかDを最初に開けるとそれ以上開ける必要はない
  • 従って適当に選んだノードの親を適当に辿るなどし、ルートっぽい(CやDのような)ノードを探索する必要がある
  • 以上をコーディングすると答えが出る

ブレイクスルー多すぎです。普通に時間内には間に合わなかったと思います。他の考え方もあるんかな・・

いずれにしても160人出して30%強の正答率なので数十人しか正解しておらず500としてはかなり難易度の高い問題と言える


(1/29追記)

親を辿ってルートっぽいのを探せば、入力辺0のものを最初に探索する必要はないのでコードはもっと単純になることが分かりました。なお最初に書いた遡り方は間違っていたのでコードを修正しています。(これでもシステムテストは通っていたのだが・・・・・)


以下、ソースです

修正版(infomationをbitに置き換えて演算しています)

O(n^4)

class CarrotBoxes {
public:
	double theProbability(vector <string> info) {
		double res=1;

		int n=info.size();

		int mincnt=n;
		//開けなくて良い箱をtとしてイテレート
		for(int t=0; t<n; t++) {
			//bit表現に変換(この時点でtを省く)
			vector <ll> binfo(n, 0);
			for(int i=0; i<n; i++) {
				if(i==t) continue;
				for(int j=0; j<n; j++) {
					if(j==t) continue;
					if(info[i][j]=='Y') binfo[i]|=(1LL<<j);
				}
			}
			//floyd-warshall
			for(int k=0; k<n; k++) {
				for(int i=0; i<n; i++) {
					for(int j=0; j<n; j++) {
						if((binfo[i]&(1LL<<k)) && (binfo[k]&(1LL<<j))) binfo[i]|=(1LL<<j);
					}
				}
			}
			//訪問済みノードをvisit[i]=1で管理
			vector <int> visit(n, 0);
			visit[t]=1;
			//未訪問ノードを探索
			int cnt=0;
			for(int i=0; i<n; i++) {
				if(visit[i]) continue;
				cnt++;
				//未訪問ノードに対し適当に親を遡る
				int bg=i;
				for(int j=0; j<n; j++) {
					if((binfo[j]&binfo[bg])==binfo[bg]) bg=j;
				}
				//未訪問ノードの先祖から訪問できるノードを全て訪問
				for(int j=0; j<n; j++) {
					if(binfo[bg]&(1LL<<j)) visit[j]=1;
				}
			}
			mincnt=min(mincnt, cnt);
		}

		res=(n-mincnt)/(double)n;
		return res;
	}
};

以下は以前書いたコード、親の遡り方が間違い(ループするとちゃんと遡れないパターンがある)

class CarrotBoxes {
public:
	double theProbability(vector <string> info) {
		double res=1;

		int n=info.size();

		int mincnt=n;
		//開けなくて良い箱をtとしてイテレート
		for(int t=0; t<n; t++) {
			//入力辺のないノードをvi[i]=0となるよう探索
			vector <int> vi(n, 0);
			for(int i=0; i<n; i++) {
				if(i==t) continue;
				for(int j=0; j<n; j++) {
					if(j==t) continue;
					if(i==j) continue;
					if(info[i][j]=='Y') vi[j]=1;
				}
			}
			//入力辺のないノードから訪問できるノードをvisit[i]=1で管理
			vector <int> visit(n, 0);
			visit[t]=1;
			for(int i=0; i<n; i++) {
				if(vi[i] || visit[i]) continue;
				queue <int> q;
				q.push(i);
				visit[i]=1;
				while(!q.empty()) {
					int qt=q.front(); q.pop();
					for(int j=0; j<n; j++) {
						if(info[qt][j]=='N') continue;
						if(visit[j]) continue;
						q.push(j);
						visit[j]=1;
					}
				}
			}
			//入力辺のないノードからでは訪問できないノード(ループを形成するノード)を探索
			int cnt=0;
			for(int i=0; i<n; i++) if(i!=t && vi[i]==0) cnt++;
			for(int i=0; i<n; i++) {
				if(visit[i]) continue;
				//訪問できてないノードに対し適当に親を遡る(変数bg)
				//この部分を省略するとWA
				//反例:以下のようなグラフ:
				//	A->B, B->A, C->A, C->D, D->C
				//	 CやDから訪問すると最適だがAやBから訪問すると2度手間になる
				int bg=i;
				vector <int> visit2(n, 0);
				visit2[bg]=1;
				for(int j=0; j<n; j++) {
					for(int k=0; k<n; k++) {
						if(bg==k) continue;
						if(visit2[k]) continue;
						if(info[k][bg]=='Y') {
							bg=k;
							visit2[bg]=1;
							break;
						}
					}
				}
				//訪問できてないノードの先祖(=bg)から訪問できるノードを全て訪問
				queue <int> q;
				q.push(bg);
				visit[bg]=1;
				cnt++;
				while(!q.empty()) {
					int qt=q.front(); q.pop();
					for(int j=0; j<n; j++) {
						if(info[qt][j]=='N') continue;
						if(visit[j]) continue;
						q.push(j);
						visit[j]=1;
					}
				}
			}
			mincnt=min(mincnt, cnt);
		}

		res=(n-mincnt)/(double)n;
		return res;
	}
};

AkshayAkshay2013/02/16 22:43This is the peercft post for me to find at this time

fmsxxkqfmsxxkq2013/02/18 05:16cyP1oT , [url=http://xumbuxjdrfyr.com/]xumbuxjdrfyr[/url], [link=http://zreanbrrqnwm.com/]zreanbrrqnwm[/link], http://xdivklnewdbg.com/

ryzincryzinc2013/02/19 14:04fQHNP4 <a href="http://lwdlhcdpomaw.com/">lwdlhcdpomaw</a>

indkdahindkdah2013/02/19 19:14zwiioO , [url=http://crmdrspswgmq.com/]crmdrspswgmq[/url], [link=http://vfasoeacrate.com/]vfasoeacrate[/link], http://zdjmdopeoupz.com/

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