Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-10-13SRM521 Div1

SRM521 Div1 250 MissingParentheses

| 00:43 | SRM521 Div1 250 MissingParentheses - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM521 Div1 250 MissingParentheses - SRM diary(Sigmar) SRM521 Div1 250 MissingParentheses - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

何か左括弧と右括弧の数の差を取ればいいような気がするが・・

絶対反例ありそう。

・・・

あった。")("←こんなやつ。

えーと・・・左から順番に見て行って、閉じられてない左括弧の数を覚えておけば良いかな

で、閉じられてない左括弧数がマイナスになると、左端に左括弧が必要だから解を+1して左括弧数を0にする。

書けた。

サンプル合った。

提出。


ついでに左括弧と右括弧の数の差を取るプログラムを書いてみる。

こちらもサンプルは全部通る。

反例がチャレンジで使えることが分かった。チャレンジ祭りになりそう。


チャレンジフェーズ

分かりやすいやつは一瞬で誰かに落とされてしまった。

でも2人おかしい人が残っていたので+100。1ミスして-25。儲かった。


ソースコード

class MissingParentheses {
public:
	int countCorrections(string par) {
		int res=0;

		int n=par.size();

		int l=0;
		for(int i=0; i<n; i++) {
			if(par[i]=='(') l++;
			else {
				if(l<=0) res++;
				else l--;
			}
		}
		res+=abs(l);//absである必要は全くない
		return res;
	}
};

prosho007prosho0072011/10/14 13:33赤おめでとうございます!

kojingharangkojingharang2011/10/14 17:46すごいっす、おめでとうございます~

SigmarSigmar2011/10/14 21:54prosho007さん、kojingharangさん、ありがとうございます!
何とかこの色を維持できるよう頑張ります。

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111013