Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-02-11SRM497 Div1

SRM497 Div1 250 PermutationSignature

| 01:10 | SRM497 Div1 250 PermutationSignature - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM497 Div1 250 PermutationSignature - SRM diary(Sigmar) SRM497 Div1 250 PermutationSignature - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

どう見ても探索は無理そうな雰囲気

サンプル見た感じだと、昇順に並べた後、連続するDのところを単に全部reverseすればいいだけに見える

うーん・・反例も思いつかないし多分合ってるだろう

書いた

サンプル合った

提出


ソースコード

class PermutationSignature {
public:
	vector <int> reconstruct(string sig) {
		vector <int> res;
		int n=sig.size()+1;
		sig.push_back('I');

		for(int i=0; i<n; i++) {
			res.push_back(i+1);
		}
		int d=0;
		int prev=0;
		for(int i=0; i<n; i++) {
			if(sig[i]=='D') {
				if(d==0) {
					d=1;
					prev=i;
				}
			} else {
				if(d==1) {
					d=0;
					reverse(res.begin()+prev, res.begin()+i+1);
				}
			}
		}
		return res;
	}
};

SRM497 Div1 550 CssRules

| 01:10 | SRM497 Div1 550 CssRules - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM497 Div1 550 CssRules - SRM diary(Sigmar) SRM497 Div1 550 CssRules - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

面倒くさい系か・・

パースさえできれば単純なメモ化再帰ぽい(ここで"#id tagName"のCSSルールが1タグ配下で同時に1つしか定義できないと勘違いする)

こういうタグのパースは何回か解いたことがある。

構文誤りがないことが保証されている場合、実は閉じる側のタグの種類は調べる必要がないのでコーディングは楽になる

ということで適当にstringを分割して解析するだけだ・・

(約30分後)

時間かかったがパースできた

後は再帰するだけ・・

(約10分後)

書いた

サンプル合った

提出

・・・

・・・

本当に合ってるんだろうか

あれ・・・間違ってる・・(勘違いに気づく)

残り5分しかないし・・・・・・・直せない・・・

同じ間違いをしてる人を落とすためにチャレンジケースでも作るか・・・


チャレンジフェーズ

トップの赤い人が同じ間違いしてる!!!

+50

そして自分のも誰かに撃墜される


後で

タグごとに色が7種類あるので色なしを含めて8^3*ノード数(100くらい?)のメモ化になりますね。

勘違いしてなければ特に難しくもないし解けたかなぁ・・相変わらず変な勘違いばかりして勿体無い・・・・・

以下、ソースコードです。

//delimを区切り文字としてstringをvector <string>に分割
vector <string> strspltos(string str, char delim) {
	vector <string> res;
	stringstream ss(str);
	string s;
	while(getline(ss, s, delim)) {
		if(ss.fail()) continue;
		res.push_back(s);
	}
	return res;
}

//タグをIDに変換
int calctagid(char c) {
	if(c=='b') return 0;
	if(c=='u') return 1;
	if(c=='i') return 2;
	cerr << "Tag Exception\n";
	throw;
}

//色をIDに変換
int calccolorid(string s) {
	if(s=="black") return 0;
	if(s=="blue") return 1;
	if(s=="gray") return 2;
	if(s=="green") return 3;
	if(s=="red") return 4;
	if(s=="white") return 5;
	if(s=="yellow") return 6;
	cerr << "Color Exception\n";
	throw;
}

vector <int> dad;
vector <int> tag;
vector <int> color;
vector <vector <int> > child;
int n;
int memo[1000][8][8][8];

class CssRules {
public:
	//再帰関数
	int rec(int d, int tagcol[3]) {
		int res=1000000000;
		int inc=0;
		if(tagcol[tag[d]]!=color[d]) inc=1;
		if(child[d].empty()) {
			return inc;
		}

		int bc=tagcol[0], uc=tagcol[1], ic=tagcol[2];

		if(memo[d][bc][uc][ic]>=0) return memo[d][bc][uc][ic];

		for(int nbc=0; nbc<8; nbc++) {
			if(nbc==7 && bc!=7) continue;
			for(int nuc=0; nuc<8; nuc++) {
				if(nuc==7 && uc!=7) continue;
				for(int nic=0; nic<8; nic++) {
					if(nic==7 && ic!=7) continue;
					int tres=(nbc!=bc)+(nuc!=uc)+(nic!=ic)+inc;
					tagcol[0]=nbc; tagcol[1]=nuc; tagcol[2]=nic;
					for(int i=0; i<(int)child[d].size(); i++) {
						tres+=rec(child[d][i], tagcol);
					}
					res=min(res, tres);
				}
			}
		}
		tagcol[0]=bc; tagcol[1]=uc; tagcol[2]=ic;

		memo[d][bc][uc][ic]=res;
		return res;
	}

	//xthmlって作者スペルミス・・
	int getMinimalCssRuleCount(vector <string> xthml) {
		int res=0;

		memset(memo, -1, sizeof(memo));
		dad.clear();
		tag.clear();
		color.clear();
		child.clear();

		//パース
		string s=accumulate(xthml.begin(), xthml.end(), string());
		vector <string> vs=strspltos(s, '>');
		n=vs.size()/2;
		dad.assign(n, -1);//親
		tag.resize(n);
		color.resize(n);
		child.resize(n);

		int stk[1000];
		int stkat=-1;
		int idx=0;
		for(int i=0; i<n*2; i++) {
			if(vs[i][1]=='/') {
				stkat--;
			} else {
				if(stkat>=0) dad[idx]=stk[stkat];
				tag[idx]=calctagid(vs[i][1]);
				vector <string> vs2=strspltos(vs[i], ' ');
				color[idx]=calccolorid(vs2[2].substr(13, vs2[2].size()-1-13));
				stkat++;
				stk[stkat]=idx;
				idx++;
			}
		}
		for(int i=0; i<n; i++) {
			if(dad[i]>=0) {
				child[dad[i]].push_back(i);
			}
		}

		//b, u, iのタグの色を全て未定(7)で初期化して再帰関数実行
		int tagcol[3];
		tagcol[0]=tagcol[1]=tagcol[2]=7;
		for(int i=0; i<n; i++) {
			if(dad[i]==-1) {
				res+=rec(i, tagcol);
			}
		}

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