SRM586 Div1 Easy "PiecewiseLinearFunction"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12691
訳
Fは区間[1,N]での実数をとり、それに対応する実数を返す関数である。あなたはN個の要素を持つint Yが与えられる。それはF(i) = Y[i-1] ( 1 <= i <= N )というように、関数Fの返す値を表している。加えて、Fは区分で直線的であることが分かっている。すなわち、区間[i,i+1]で、Fは直線的な値を返す。関数Fは、これらの情報により、返す値が一意に定まる。例えば、F(4)=1でF(5)=6であれば、F(4.7)=4.5となる。
別の例を示す。例えばY={1, 4, -1, 2}であれば、下図のようになる。
実数yが与えられたとき、F(x) = yであるポイントの数を数え上げる事が出来る。例えば、関数Fが、上記のような状態のとき、y=7では0個、y=4のときは1個、そしてy=1.1のときは3個、そのようなポイントがある。このポイントが最も多くなるyを探し、ポイントの数を返せ。上記の例であれば返す値は3となるだろう。
制約
2 <= Yの要素数 <= 50
-10^9 <= Y[i] <= 10^9
考えた事(ヒント参照後)
ポイントが増えたり減ったりする所は各iのY[i]の部分なので、そのyと、プラマイ0.5のyを調べてあげればよい。
事後
他の人のブログに0.5って書いてあったのをチラ見しちゃった
ソースコード
class PiecewiseLinearFunction { public: int maximumSolutions(vector <int> Y){ int N = Y.size(); // 試す候補を選定 vector<double> cand; for( int i = 0; i < N; i++ ){ cand.push_back( Y[i] - 0.5 ); cand.push_back( Y[i] ); cand.push_back( Y[i] + 0.5 ); } int best = 0; bool INF = false; for( int i = 0; i < cand.size(); i++ ){ double y = cand[i]; int res = 0; for( int j = 0; j < N - 1; j++ ){ if( Y[j] == Y[j+1] ){ INF = true; } if( Y[j] <= y && y < Y[j+1] ){ res++; } if( Y[j+1] < y && y <= Y[j] ){ res++; } } if( y == Y[N-1] ) res++; best = max( best, res ); } return INF ? -1 : best; } };