読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

SRM586 Div1 easy

問題概要:略

解法:
各ノードに対して Y[i]を+0.5,0.0,-0.5したx軸と平行な直線を引いて何本と交差するか確かめる
単純にY[i]だけでやると 0 1 0 1 0 1 みたいなときに誤って3と出力してしまう


コード:::

double err[] = {0.5,0.0,-0.5};

class PiecewiseLinearFunction {
public:

  
  int maximumSolutions(vector <int> Y) {
    int ysize = Y.size();
    REP(i,1,ysize)if(Y[i] == Y[i-1])return -1;
    int ans = 0;

    rep(k,3)
      {
	rep(i,ysize)
	  {
	    int cnt = 0;
	    ld trg = (ld)Y[i] + err[k];
	    if(trg == Y[0])cnt++;
	    REP(j,1,ysize)
	      {
		if(Y[j-1] > Y[j] && (Y[j-1] > trg && trg >= Y[j]))cnt++;
		else if(Y[j-1] < Y[j] && (Y[j-1] < trg && trg <= Y[j]))cnt++;
	      }
	    ans = max(ans,cnt);
	  }
      }
    
    return ans;
  }
};