SRM586 Div2 Medium "PiecewiseLinearFunctionDiv2"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12698
訳
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となる。
あなたはまた、int queryが与えられる。それぞれのiで、F(x) = query[i]となる場所の数を計算せよ。ただし、この数は無限大になる可能性があることに注意せよ。その場合、結果は-1とすること。
制約
2 <= Yの要素数 <= 50
-10^9 <= Y[i] <= 10^9
1 <= queryの要素数 <= 50
-10^9 <= query[i] <= 10^9
考えた事
ちょうど頂点にかすって当たっている場所を、重複して数えないように、[ Y[j], Y[j+1] )にquery[i]が通っているかを判定してやればよい。
query[i] == Y[j] かつ Y[j] == Y[j+1]となるものがあれば、query[i]の結果は無限大になる。
ソースコード
class PiecewiseLinearFunctionDiv2 { public: vector <int> countSolutions(vector <int> Y, vector <int> query){ int N = Y.size(); int M = query.size(); vector<int> ans; for( int i = 0; i < M; i++ ){ int res = 0; int y = query[i]; for( int i = 0; i < N - 1; i++ ){ if( Y[i] == y && Y[i+1] == y ){ res = -1; break; } if( Y[i] <= y && y < Y[i+1] ){ res++; } if( Y[i+1] < y && y <= Y[i] ){ res++; } } if( res != -1 && Y[N-1] == y ) res++; ans.push_back( res ); } return ans; } };