Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-04-20SRM540 Div1

SRM540 Div1 250 ImportantSequence

| 16:55 | SRM540 Div1 250 ImportantSequence - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM540 Div1 250 ImportantSequence - SRM diary(Sigmar) SRM540 Div1 250 ImportantSequence - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

1つ決めると後は全部決まるのはすぐ分かったけど、それでどうすればいんだっけ・・

+がなければ明らかに上限がなくて解が無限にあるから、+のところで区間を区切って考えるのかなあ

何となく+のところで区切った区間ごとに上限と下限を出してみようとしてみる

区間同士はどうやって結合すればいいんだ・・・

あー、実は+のところは上限と下限を反転するだけなのか

じゃあ、区間ごとに区切らなくても、左端の要素から右へ順番になぞって、上限と下限を段々狭めていけばいいのか

書いた

時間かかりすぎた。提出。

あー部分的に0を返す判定が抜けてる・・まあ最後にも判定してるから大丈夫かな。。


チャレンジフェーズで勘違いしてオーバーフローしそうだと思ったけどしなかったんで-50点くらってしまった

ちゃんと見てから投げよう・・・


ソースコード

class ImportantSequence {
public:
	int getCount(vector <int> B, string op) {
		int res;
		int n=B.size();
		int finite=false;
		for(int i=0; i<n; i++) {
			if(op[i]=='+') finite=true;
		}
		if(!finite) return -1;

		ll maxv=1000000000000000000LL, minv=1;
		for(int i=0; i<n; i++) {
			if(op[i]=='-') {
				maxv-=B[i];
				minv-=B[i];
				if(minv<=0) minv=1;
				//ここに if(maxv<=0) return 0; もあったほうが良かったかな
			} else {
				if(minv>=B[i]) return 0;
				if(maxv>=B[i]) maxv=B[i]-1;
				swap(maxv, minv);
				maxv=B[i]-maxv;
				minv=B[i]-minv;
			}
		}
		
		res=maxv-minv+1;
		if(res<0) res=0;
		return res;
	}
};

KelisKelis2012/11/15 02:30Me and this atircle, sitting in a tree, L-E-A-R-N-I-N-G!

vsolmndcevsolmndce2012/11/15 12:352t3kuC <a href="http://jkxotjkfkoqx.com/">jkxotjkfkoqx</a>

lzxslcbfdclzxslcbfdc2012/11/16 11:02lsMjkV , [url=http://pswxdpjynsds.com/]pswxdpjynsds[/url], [link=http://dfyzalsrkwwt.com/]dfyzalsrkwwt[/link], http://rcymvzaqhavf.com/

hzezocyuybrhzezocyuybr2012/11/17 21:21SC9H6Q , [url=http://pczvhtfxmuwm.com/]pczvhtfxmuwm[/url], [link=http://zqyfpyiuonso.com/]zqyfpyiuonso[/link], http://nudkivwjzsgg.com/

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