Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-05-15TCO2011 Qual1

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