TopCoder, SRM 635, Division 1, Level 1 : SimilarRatingGraph

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13485&rd=16078

問題概要

　レーティングラフとは点の列である。
　グラフ上の区間とは、点列の連続する部分列である。二つの異なる区間について、平行移動と拡大・縮小のみによって一方から他方に一致するものを作れるとき、この二つの区間は「似ている」とする。区間の長さは、区間に含まれる点の内、隣り合うもの同士を接続した線分の長さの和として定義する。
　レーティンググラフが与えられる。 番目の点は にある。与えられたグラフ内の区間であって、それと異なる区間と「似ている」ものの長さの最大値を求めよ。
　

解法

　 を と書きます。
　二つの区間を固定したとすると、横方向の長さ（ の最大値と最小値の差）の比から相似比が求まるので、あとは傾きなどから「似ている」かどうかの判定ができそうですが、これは全体で になって TLE してしまいます。基本的な考え方は同じですが、より効率的な求め方を考える必要があります。
　ある「似ている」二つの区間があったとします。これらの区間の末尾を 1 ずつ伸ばしても「似ている」のであれば、伸ばす前の状態は明らかに最適解になりません。このように始点のみを決めて（＝要素数 1 の区間を決めて）から伸ばせるだけ伸ばすことで、仮定された始点から達成できる最大の区間を計算できます。始点の取り方を全部試しても、区間を伸ばす処理をある程度高速にできれば時間内に解けそうです。
　では、2 つの区間の先頭だけを決めたとします。始点のインデックスをそれぞれ とすると、（点が重ならなければならないということから）2 番目の点までの幅を使って相似比を計算できます。相似比を とすれば、 です。この相似比を使って、2 番目以降の各点を区間に追加できるか判定していきます。（ を始点とする区間で言うと） 番目までの点を区間に追加して、 番目の点を追加しようとしているとき、次の点を追加できるだめの条件は 2 つあって、

• 横方向の幅が相似比 で相似 :
• 区間末尾から次の点までの結ぶ線分の傾きが等しい :

の両方を満たさなければなりません。この両方を満たすとき、確定している区間の末尾と次の点との関係は、同じ相似比で相似であると言え、次の点を末尾にくっつけても全体は相似のままとなります。1 個の点について追加可能かを判定するのを でできるので、ある全ての始点の組に対して最大の区間を求める処理は でできます。
　あとは、始点のペアに対して求まる最大の区間のそれぞれを解候補として、それぞれの長さを計算して最大値をとれば、問題を解けます。

コード

using VI = vector<int>;
template < typename T = int > using VT = vector<T>;

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

#include <complex>
using Point = complex< double >;

constexpr double EPS = 1e-15;

class SimilarRatingGraph
{
public:
	double maxLength( vector <int> date, vector <int> rating )
	{
		const int N = date.size();

		VT< double > distance( N - 1 );
		REP( i, 0, N - 1 )
		{
			distance[i] = abs( Point( date[i], rating[i] ) - Point( date[ i + 1 ], rating[ i + 1 ] ) );
		}

		double res = 0;
		REP( i, 0, N - 1 )
		{
			REP( j, 0, N - 1 )
			{
				if ( i == j )
				{
					continue;
				}

				const int l = solve( date, rating, i, j );
				double tmp = 0;
				REP( k, i, i + l )
				{
					tmp += distance[k];
				}
				res = max( res, tmp );
			}
		}

		return res;
	}

	int solve( const VI &date, const VI &rating, const int a, const int b )
	{
		const int N = date.size();
		const double ratio = 1. * ( date[ a + 1 ] - date[a] ) / ( date[ b + 1 ] - date[b] );

		int l;
		for ( l = 0; a + l + 1 < N && b + l + 1 < N; ++l )
		{
			const int dda = date[ a + l + 1 ] - date[ a + l ], ddb = date[ b + l + 1 ] - date[ b + l ];
			const int dra = rating[ a + l + 1 ] - rating[ a + l ], drb = rating[ b + l + 1 ] - rating[ b + l ];
			if ( EPS < abs( dda - ratio * ddb  ) ||
				 EPS < abs( 1. * dra / dda - 1. * drb / ddb ) )
			{
				break;
			}
		}

		return l;
	}
};