TopCoder SRM 787 : Div1 Easy AqaAsadiMinimizes

反省事項の多い回。
https://community.topcoder.com/stat?c=problem_statement&pm=16197&rd=17994

問題

N要素の整数列Aが与えられる。(i,A[i])をN点プロットしたとき、2点を結ぶ直線の傾きの絶対値の最小値を求めよ。

解法

二分探索解もあるが、もっと簡単な解法もある。
Y座標の大きい順に点をソートし、隣接点間の傾きを総当たりすればよい。

class AqaAsadiMinimizes {
	public:
	
	
	double getMin(vector <int> P, int B0, int X, int Y, int N) {
		vector<ll> A;
		vector<pair<ll,int>> V;
		int i;
		
		FOR(i,N) {
			if(i<P.size()) {
				A.push_back(P[i]);
			}
			else if(i==P.size()) {
				A.push_back(B0);
			}
			else {
				A.push_back((A.back()*X+Y)%1000000007);
			}
			V.push_back({A.back(),i});
		}
		sort(ALL(V));
		
		double ret=1e10;
		FOR(i,N-1) {
			ret=min(ret,1.0*(V[i+1].first-V[i].first)/abs(V[i].second-V[i+1].second));
		}
		
		return ret;
		
		
	}
}

まとめ

本番考えすぎたな…。