POJ 2601 - Simple calculations

http://poj.org/problem?id=2601

概要

n+2 個の要素からなる数列 a[0], ..., a[n+1] を

a[i] = (a[i-1] + a[i+1])/2 - c[i]

と定める．

a[0], a[n+1], c[1], ..., c[n] が与えられたとき，a[1] の値を答える．

制約

• n <= 3000

解法

漸化式を解くと

a[1] = (a[n+1] + n*a[0] - 2*Σ((n-i)*c[i]))/(n+1)

となるので，これを計算するだけ．

あるいは a[1] の値に対して a[n+1] は単調に増加することを利用して二分探索という方法もある．

 1 #include <cstdio>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6   int n;
 7   double a0, an1;
 8   scanf("%d %lf %lf", &n, &a0, &an1);
 9   double c_sum = 0.0;
10   for (int i = 0; i < n; i++) {
11     double c;
12     scanf("%lf", &c);
13     c_sum += (n-i) * c;
14   }
15   printf("%.2f\n", (an1 + n*a0 - 2*c_sum)/(n+1));
16   return 0;
17 }