TopCoder SRM 586 Div1 Easy PiecewiseLinearFunction

この日Codeforces #184とSRM586連戦。
Codeforcesでまさかの0完をやらかしてしまったが、その後のSRMではEasy・Mediumを解いて１チャレンジを決め、赤コーダーも数名いる中でまさかのRoom Leader。
CFでレート大幅減、SRMでレート大幅増でレートがひっくり返った。

ではEasyから。
http://community.topcoder.com/stat?c=problem_statement&pm=12691

問題

２次元座標上において、配列Yが与えられる。
(1,Y[1])(2,Y[2])…(N,Y[N])を順につないだ折れ線グラフf(x)を考えたとき、X軸と平行に引いた線でf(x)との交点の最大数を求めよ。

解法

Yの範囲がかなり広い。
本番、自分はYを0～2Nまでの偶数に座標圧縮して、各整数yについてf(x)=yを求めた。
それが下記コード。

でも、後で考えたら座標圧縮しなくても、まずYを倍にして偶数にしておき、各Y[i]-1、Y[i]、Y[i]+1あたりを調べれば十分だと気付いた。
まぁ正解したからいいけど。

class PiecewiseLinearFunction {
	int N;
	vector<int> V;
	public:
	int maximumSolutions(vector <int> Y) {
		int i,j;
		N=Y.size();
		
		V.clear();
		FOR(i,N) V.push_back(Y[i]);
		sort(V.begin(),V.end());
		V.erase(unique(V.begin(),V.end()),V.end());
		FOR(i,N) {
			FOR(j,V.size()) {
				if(Y[i]==V[j]) {
					Y[i]=j*2;
					break;
				}
			}
		}
		FOR(i,N-1) if(Y[i]==Y[i+1]) return -1;
		
		int ma=0,y;
		for(y=-100;y<=200;y++) {
			int jj=0;
			FOR(i,N-1) {
				if(Y[i]==y || (Y[i]<y && Y[i+1]>y) || (Y[i]>y && Y[i+1]<y)) jj++;
			}
			if(Y[N-1]==y) jj++;
			ma=max(ma,jj);
			
		}
		return ma;
	}
};

まとめ

この問題、妙にAC率低かったけど何が問題だったんだろ。