WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
        
    }
};