UnKoder #03 : Urbanity

２問目よりずっと簡単でした。
https://www.hackerrank.com/contests/unkoder-03/challenges/urbanity

問題

N個の町があり、それぞれの位置はX[i]（昇順）である。
i番の町の都会度は定数aを用いてで定義される。

各町の都会度を算出せよ。

解法

i番について、i番より手前の町jとの間で計算される都会度g(i)を考える。

だが、これは変形すると
と表現できることに気づく。
よってで順次計算できる。

i番より奥の町jとの間で計算される都会度h(i)を考えると、こちらも同様にで順に計算できる。
後はを答えるだけ。

int N;
double A;
ll X[101000];
double R[101000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A;
	FOR(i,N) cin>>X[i];
	
	double c=0;
	for(i=1;i<N;i++) {
		c = pow(A,X[i]-X[i-1])*(c+1);
		R[i] += c;
	}
	c=0;
	for(i=N-2;i>=0;i--) {
		c = pow(A,X[i+1]-X[i])*(c+1);
		R[i] += c;
	}
	
	FOR(i,N) _P("%.12lf\n",R[i]);
	
}

まとめ

こちらはすぐ解法が浮かんだ。