torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder SRM 586, Division 1, Level 1 : PiecewiseLinearFunction

概要

関数 f があり、そのうちいくつかの点、( x, f(x) ) の座標は ( i, Y[i] ) である。
関数は ( i, Y[i] ) と( i + 1, Y[ i + 1 ] ) を結んだ線分の集合となる。
関数の定義域は [ 1, Y.size ] である。

y = f(x) を満たす x の個数が最も多い y について解の個数を求めよ。
無限にある場合は -1 で示せ。

解法

まず、配列 Y に於いて隣り合う要素同士が等しい箇所が一つでもあれば、X 軸に平行な線分が存在します。
その線分上に点を無限に置くことができるので、この場合は -1 です。
それ以外のときは必ず有限個の解しかもてません。

解が有限個であることが分かった条件下で、最も多くの解を与える y を探す方法について考えます。
関数の値域がかなり広い上に実数関数なので全探索することはできません。
しかし、高々有限個の y について調べればよいことが示せます。
というのも、f が折れ曲がる場所は必ず整数点なので、整数 k があって y が ( k, k + 1 ) の区間内で動いたとしても解の個数は変わりません。
なので、非整数点については ( k, k + 1 ) の区間から代表値を一つだけ調べればよいことが分かります。

これで実数関数であることによる問題は無くなりましたが、また定義域が広いことによる問題があります。
しかしこれも、同じような考え方で解消することができます。
Y をソートしたものを Y' とします。
このとき、y の値を ( Y'[i], Y'[ i + 1 ] ) の区間内で動かしても解の個数は変わりません。

まとめると、各 i について Y[i] - 0.5, Y[i], Y[i] + 0.5 の三つを解候補の y として調べれば十分であることが言えます。

実装についてですが、0.5 を普通に加減すると浮動小数点になって誤差が怖いです。
そこで、元の Y 座標を全て二倍して扱うと 0.5 を奇数( ∈ 整数 )として扱えるので誤差の心配がいらなくなります。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define PB push_back

class PiecewiseLinearFunction
{
public:
	int maximumSolutions( vector <int> Y )
	{
		const int N = Y.size();
		VI ys;

		REP( i, 0, N )
		{
			Y[i] *= 2;
			REP( j, -1, 2 )
			{
				ys.PB( Y[i] + j );
			}
		}
		
		REP( i, 0, N - 1 )
		{
			if ( Y[i] == Y[ i + 1 ] )
			{
				return -1;
			}
		}

		int res = 0;
		REP( i, 0, ys.size() )
		{
			int tmp = 0;
			REP( j, 0, N - 1 )
			{
				tmp += min( Y[j], Y[ j + 1 ] ) <= ys[i] && ys[i] <= max( Y[j], Y[ j + 1 ] );
			}
			REP( j, 1, N - 1 )
			{
				tmp -= Y[j] == ys[i];
			}
			res = max( res, tmp );
		}
		return res;
	}
};