Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-08-21SRM515 Div1

SRM515 Div1 250 RotatedClock

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

Problem Statement

コーディングフェーズ

適当にイテレーションすればOK

問題読解でみんな時間がかかっていた模様?


ソースコード

class RotatedClock {
public:
	string getEarliest(int hour, int minute) {
		string res;

		for(int i=0; i<12; i++) {
			int bias=30*i;
			int h=hour, m=minute;
			while(h<bias) {
				h+=30;
				m+=30;
			}
			while(h>=bias+30) {
				h-=30;
				m-=30;
			}
			m=(m+360)%360;
			if(m*30==(h-bias)*360) {
				h/=30;
				m/=6;
				stringstream ss;
				ss << setw(2) << setfill('0') << h;
				res+=ss.str()+":";
				ss.clear(); ss.str("");
				ss << setw(2) << setfill('0') << m;
				res+=ss.str();
				return res;
			}
		}
		return res;
	}
};

SRM515 Div1 550 NewItemShop

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

Problem Statement

コーディングフェーズ

1時間に来るのは最大1人だよとわざわざっぽく書いてあるのでこれが重要なんだろう(英語的にすこし読み取りにくいが・・)

2箇所以上来る可能性があるのは最大12人になるから、2^12でビットDPとかかな

書いてみた

結構バグっていてデバッグに時間を取られてしまったができた

何か別に考え方は難しくないような・・・どの辺が550なんだろう

提出

あれ、ルーム内誰も出してない。なぜに・・

もう1回見直す。13人以上いるときのビットの更新方法が間違っていることに気づく。しまった・・

直して再提出。今度は大丈夫そう。出す前にもっとちゃんと見なおさないとダメだ

サンプルには13人以上いるものがないので、これはチャレンジポイントになるかもしれない。


と思ったが、自分以外は全員mapを使ったDP/メモ化だったので突っ込みどころがなかった

mapで計算量大丈夫なのかという気もするが、なかなか見積もりが難しく落とせるか判断つかない

チャレンジフェーズが始まった瞬間550が2人落とされたんだけど、絨毯爆撃しているわけでもなかったのでどういう判断で突撃したのか

不思議・・・


ソースコード

template <class T> vector <T> strspl(string str) {
	vector <T> res;
	istringstream iss(str);
	copy(istream_iterator <T>(iss), istream_iterator <T>(), back_inserter(res));
	return res;
}

double memo[25][1<<12][25];

class NewItemShop {
public:
	int n;
	int many;
	vector <vector < vector <int> > > c;
	vector <int> t, ti;
	int swords;

	double rec(int d, int mask, int rem) {
		if(d>=24) return 0;
		if(t[d]==-1) return rec(d+1, mask, rem);

		if(t[d]<many && (mask&(1<<t[d]))) return rec(d+1, mask, rem);

		if(memo[d][mask][rem]>=0) return memo[d][mask][rem];

		int sp=100;
		for(int i=0; i<ti[d]; i++) {
			sp-=c[t[d]][i][2];
		}
		double p=(double)c[t[d]][ti[d]][2]/sp;

		int nmask=mask;
		if(t[d]<many) nmask|=(1<<t[d]);
		double r1=rec(d+1, mask, rem)*(1-p);
		double r2=rec(d+1, nmask, rem)*p;
		double r3=0;
		if(rem>0) r3=(rec(d+1, nmask, rem-1)+c[t[d]][ti[d]][1])*p;
		double res=r1+max(r2, r3);

		memo[d][mask][rem]=res;
		return res;
	}

	double getMaximum(int _swords, vector <string> custom) {
		double res;
		swords=_swords;
		n=custom.size();
		c.clear();
		vector <vector <vector <int> > > cc(n);

		for(int i=0; i<n; i++) {
			vector <string> vs=strspl <string>(custom[i]);
			for(int j=0; j<(int)vs.size(); j++) {
				for(int k=0; k<(int)vs[j].size(); k++) if(vs[j][k]==',') vs[j][k]=' ';
				vector <int> vi=strspl <int>(vs[j]);
				cc[i].push_back(vi);
			}
		}

		for(int i=0; i<n; i++) {
			if(cc[i].size()>1) c.push_back(cc[i]);
		}
		many=c.size();
		for(int i=0; i<n; i++) {
			if(cc[i].size()==1) c.push_back(cc[i]);
		}

		t.clear();
		t.assign(24, -1);
		ti.clear();
		ti.resize(24);
		for(int i=0; i<n; i++) {
			for(int j=0; j<(int)c[i].size(); j++) {
				t[c[i][j][0]]=i;
				ti[c[i][j][0]]=j;
			}
		}

		memset(memo, -2, sizeof(memo));
		res=rec(0, 0, swords);
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110821