Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-05-15TCO2011 Qual1

  • 250:245.84, 500:445.39, 1000:Opened, score:691.23, rank:80, rating:2099(+49)
  • 1000の通過率が低く、チャレンジ勝負のような回になってしまったがチャレンジできず

TCO2011 Qual1 250 MinimumLiars

| 14:25 | TCO2011 Qual1 250 MinimumLiars - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Qual1 250 MinimumLiars - SRM diary(Sigmar) TCO2011 Qual1 250 MinimumLiars - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

流石に全探索するだけ


ソースコード

class MinimumLiars {
public:
	int getMinimum(vector <int> claim) {
		int res=-1;
		int n=claim.size();

		for(int i=0; i<=n; i++) {
			int cnt=0;
			for(int j=0; j<n; j++) {
				if(claim[j]>i) cnt++;
			}
			if(cnt==i) return i;
		}

		return res;
	}
};

TCO2011 Qual1 500 FoxListeningToMusic

| 14:25 | TCO2011 Qual1 500 FoxListeningToMusic - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Qual1 500 FoxListeningToMusic - SRM diary(Sigmar) TCO2011 Qual1 500 FoxListeningToMusic - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

何となく、曲の終わるタイミングが時間tである確率をDPすれば良さそうである

書いた

サンプル合った

提出


ソースコード

class FoxListeningToMusic {
public:
	vector <double> getProbabilities(vector <int> len, int T) {
		vector <double> res;
		int n=len.size();
		res.assign(n, 0);

		double dp[80010];
		memset(dp, 0, sizeof(dp));
		dp[0]=1;
		for(int t=0; t<=T; t++) {
			for(int i=0; i<n; i++) {
				if(t+len[i]>T) res[i]+=dp[t]/n;
				else dp[t+len[i]]+=dp[t]/n;
			}
		}
		return res;
	}
};

TCO2011 Qual1 1000 SquareSeries

| 14:25 | TCO2011 Qual1 1000 SquareSeries - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Qual1 1000 SquareSeries - SRM diary(Sigmar) TCO2011 Qual1 1000 SquareSeries - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

簡単そうでややこしい

何となく、BBBBBとかWWWWWとかBWBWBWBWとかWBWBWBWBとかのパターンにしかならなさそう

ただし最初と最後だけ任意のパターンが出てきそうな気がする

しかしそれで本当に合うか分からなかったのでDPすることにした

実装が大変・・・

書ききれず・・・


ソースコード

後でプラクティスで通した

計算量を多少無駄にしても簡単に書くのがまだ少しできていない

こういうのちゃんと整理して書けるようにならないと・・・

class SquareSeries {
public:
	int calclen(string s) {
		if(s.empty()) return 0;
		int res=1;
		for(int i=1; i<(int)s.size(); i++) if(s[i]!=s[i-1]) res++; else res--;
		return res;
	}

	bool valid(string s, int slen) {
		int len=slen;
		for(int i=1; i<(int)s.size(); i++) {
			if(s[i]!=s[i-1]) len++; else len--;
			if(len<=0) return false;
		}
		return true;
	}

	void dpupdate(string &target, const string &source) {
		if(target.empty() || target>source) target=source;
	}

	string completeIt(string pat, int lastlen) {
		string res="...";

		int qidx=pat.find('?');
		string head=pat.substr(0, qidx), tail=pat.substr(qidx+1);
		if(valid(head+tail, 1) && calclen(head+tail)==lastlen) return head+tail;

		int hlen=calclen(head);
		if(hlen<0) return res;
		char hchar=(head.empty()?' ':head[head.size()-1]);

		string dp[155][155][2];
		if(hchar!='B') dp[0][hlen][0].push_back(hchar);
		if(hchar!='W') dp[0][hlen][1].push_back(hchar);
		for(int d=0; d<154; d++) {
			for(int len=0; len<154; len++) {
				for(int col=0; col<2; col++) {
					if(dp[d][len][col].empty()) continue;
					if(col==0) {
						if(len-1>0) dpupdate(dp[d+1][len-1][0], dp[d][len][0]+"W");
						dpupdate(dp[d+1][len+1][1], dp[d][len][0]+"B");
					} else {
						if(len-1>0) dpupdate(dp[d+1][len-1][1], dp[d][len][1]+"B");
						dpupdate(dp[d+1][len+1][0], dp[d][len][1]+"W");
					}
				}
			}
		}

		int ressz=1000000000;
		for(int d=0; d<154; d++) {
			for(int len=0; len<154; len++) {
				for(int col=0; col<2; col++) {
					if(dp[d][len][col].empty()) continue;
					string tres=head+dp[d][len][col].substr(1)+tail;
					int tressz=tres.size();
					if(!valid(tres, 1) || calclen(tres)!=lastlen) continue;
					if(tressz<ressz || tressz==ressz && tres<res) {
						res=tres;
						ressz=tressz;
					}
				}
			}
		}

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