TopCoder SRM 557 Div1 Easy FoxAndMountainEasy

久々のSRM、まさかのxx-で0点やらかした…。
Mediumは元々アルゴリズムを知らなかったのでしょうがないとして、Easyは凡ミスすぎる。
チャレンジの時点でミスに気が付いて、終了後Practiceで正答。

ただ、最近のDiv1 Easyの中では正解率が54%と割と低く、やらかした人は多数いた模様。

そんなEasyを見ていきます。
http://community.topcoder.com/stat?c=problem_statement&pm=12195

山登りにおいてN個の地点があり、最初と最後の地点の高さが与えられる。
地点を１個進むと、1m上がるか1m下がるかのどちらかである。
ここで、最初から最後までの上り下りする場合に、そのうち一部のルートが文字列で与えられる。
そのようなルートを含んで最初から最後まで行く手段があるか、有無を答える。

面倒なのは、途中のルートで高さが負になってはいけないこと。
よって、含むべきルートは、できるだけ高い位置で開始するのが良い。

回答は以下の通り。

• まず、与えられたルートをたどる場合の高低差と、一番低い地点を計算する
• 与えられたルート以外の上りと下りの回数を計算する
• 開始始点から、上で計算した分上った高さが、ルートで下がる高さより大きければok、小さければng

class FoxAndMountainEasy {
	public:
	char str[100];
	int sl;
	string possible(int n, int h0, int hn, string history) {
		char *pc;
		int i,mind,difd,nu,nd,dif;
		strcpy(str,history.c_str());
		sl=strlen(str);
		
		mind=0;
		difd=0;
		FOR(i,sl) {
			if(str[i]=='U') difd++;
			else {difd--; mind=min(mind,difd);}
		}
		
		n-=sl;
		dif = hn-(h0+difd);
		if(abs(dif)>n || ((n%2)!=(abs(dif)%2))) return string("NO");
		
		// nu+nd=n, nu-nd=dif
		nu = (n + dif)/2;
		nd = (n - dif)/2;
		if(nu<0 || nd<0) return string("NO");
		if(h0+nu+mind<0) return string("NO");
		
		return string("YES");
	}
};

まとめ

本番では、なぜか一部のルートが先頭か最後じゃないとダメだと思ってしまった。
チャレンジで自分を撃墜しようと思ったけど、どうも自分を撃墜しても点にならないらしいのでやめた。
ちゃんと問題読まないとな…。