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;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110211