SRM diary(Sigmar)

SRM497 Div1 250 PermutationSignature

SRM497, Div1 | 01:10 |

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

SRM497, Div1 | 01:10 |

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;
	}
};