Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-07-18SRM476 Div1

SRM476 Div1 250 Badgers

| 13:49 | SRM476 Div1 250 Badgers - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM476 Div1 250 Badgers - SRM diary(Sigmar) SRM476 Div1 250 Badgers - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→読みにくい・・

→つまり、、2匹以上の場合のみgreed[i]だけ追加の餌が必要ということなのかな?

→あ、違う、よく読んだら他のbadger1匹につきgreed[i]の餌が追加で必要ということか

→えーと・・たかだか50匹しかいないので、x匹飼えるかどうか全部試せばOKかな

→書く→サンプル合わない

→何やら色々書き間違っている→直す→サンプル合う

→コーナーケースは・・0匹と最大匹数を確認、問題なし

→提出

→500へ


チャレンジフェーズ

→狙いどころは0と最大値のコーナーケースくらいか・・

→全員0から最大値までちゃんと見てますね

→特になにもせず


システムテスト

→Passed


以下、ソースです。

ちょっと問題読解とミス修正で時間を取りすぎた・・


class Badgers {
public:
	int feedMost(vector <int> hunger, vector <int> greed, int totalFood) {
		int res;
		int bsz=hunger.size();

		for(res=bsz; res>0; res--) {
			vector <int> f(bsz);
			for(int i=0; i<bsz; i++) {
				f[i]=hunger[i]+greed[i]*(res-1);
			}
			sort(f.begin(), f.end());
			if(accumulate(f.begin(), f.begin()+res, 0)<=totalFood) return res;
		}
		return 0;
	}
};

SRM476 Div1 550 FriendTour

| 13:49 | SRM476 Div1 550 FriendTour - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM476 Div1 550 FriendTour - SRM diary(Sigmar) SRM476 Div1 550 FriendTour - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→えーと・・・ハミルトン路のような問題かな

→確率を計算するためには、、、うーん・・全探索+DPしかない気がするけど

→ノードは最大36。36*2^36になるから、普通にDPしても無理ですね

→エッジ数は36文字で表現するので、各ノード最大15エッジになるけど・・・だから何なんだろう・・何かに使うのかな。。

→他の方法は・・(色々考える)・・・駄目だ・・解く方法がない

→とりあえず全探索してみよう。もしかしてエッジ数が少ない分、記憶容量が少なくて済むからMAPとかでDPすればいけるかも知れん。

→書く

→むぅ・・なぜかサンプルの0と1しか合わない。なぜだ・・・

→時間切れ


チャレンジフェーズ

→2^36でDPしてる人は・・いるわけないか

→特に何もせず


終了後

→何でサンプルの2番以降の答えが合わなかったんだろう。

→注意深くデバッグしてみるが・・どう見てもプログラムは合っているようにしか見えない

→何か問題の読み違えがあるのかな。もう一度よく読んでみよう。

→ん・・?

→あれ?

→「マナオは自分の友達以外のページを訪問しない」

→は・・?36人全員訪問するんじゃないんですか??

→問題文はよく読まないとダメですね。。。

→以下、修正したソースです。マナオを含めて最大16人に圧縮して全探索+DPしてます。

//stringをdelimで分割してvector <int>に変換する関数
vector <int> strspltoi(string str, const char delim) {
    vector <int> result;
    int i=0, ssize=0, prev=-1;
    string tmps;

    ssize=str.size();

    for(i=0; i<ssize; i++) {
        if(str[i] == delim) {
            tmps.assign(str, prev+1, i-prev-1);
            result.push_back(atoi(tmps.c_str()));
            prev=i;
        }
    }
    tmps.assign(str, prev+1, ssize-prev-1);
    result.push_back(atoi(tmps.c_str()));

    return result;
}

double memo[16][1<<16];

class FriendTour {
public:
	vector <vector <int> > a;//隣接行列
	vector <int> e;//各人のエッジ数
	int fsz;//友達+マナオの人数
	int K;
	map <int, int> fid;

	//dfsで全員訪問できる確率を返す
	double rec(int v, int mask) {
		double res=0;
		double tr[40]={0};

		mask=mask|(1<<v);
		if(mask==(1<<fsz)-1) return 1;
		if(memo[v][mask]>=0) return memo[v][mask];

		//まず、各エッジへ進んだ場合の成功率を保存する
		for(int i=0; i<fsz; i++) {
			if(a[v][i]==0) continue;
			if(mask&(1<<i)) continue;
			tr[i]=rec(i, mask);
		}
		sort(tr, tr+fsz, greater<double>());
		//エッジ数(e[v])がK以下なら、最も確率の高いものを返す
		if(e[v]<=K) res=tr[0];
		else {
			double rem=1;
			//確率最大エッジに進める確率はK/e[v]
			//確率最大エッジに進めない場合、確率2番目エッジに進める確率はK/(e[v]-1)...以下同様
			for(int i=1, j=0; i<=e[v]-K+1; i++, j++) {
				res+=rem*tr[j]*K/(e[v]-j);
				rem*=1-(double)K/(e[v]-j);
			}
		}
		memo[v][mask]=res;
		return res;
	}

	double tourProbability(vector <string> friends, int _K) {
		double res=0;

		K=_K;
		fid.clear();
		a.clear();
		e.clear();
		for(int i=0; i<16; i++) for(int j=0; j<(1<<16); j++) memo[i][j]=-1;

		//マナオの友達のみ抽出して隣接行列を作成する
		//隣接行列の作成(マナオ分)
		vector <int> tv=strspltoi(friends[0], ' ');
		a.push_back(vector <int>());
		a[0].push_back(0);
		fid[1]=0;
		//マナオの友達にmapでidを付与
		for(int j=0; j<(int)tv.size(); j++) {
			fid[tv[j]]=j+1;
			a[0].push_back(1);
		}
		fsz=tv.size()+1;

		//隣接行列の作成(マナオ以外)
		a.resize(fsz);
		e.resize(fsz);
		e[0]=fsz-1;
		for(int i=1; i<(int)friends.size(); i++) {
			if(!fid.count(i+1)) continue;
			a[fid[i+1]].resize(fsz);
			tv=strspltoi(friends[i], ' ');
			for(int j=0; j<(int)tv.size(); j++) {
				if(!fid.count(tv[j])) continue;
				a[fid[i+1]][fid[tv[j]]]=1;
			}
			e[fid[i+1]]=tv.size();
		}

		res=rec(0, 0);

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