WARush

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

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}であれば、下図のようになる。
f:id:Ekaing:20130806003320p:plain

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