解いた問題のソースコードと解説など。


POJ 2601 Simple calculations

問題

a_i = (a_{i-1} + a_{i+1})/2 - c_iという漸化式の数列がある。a_0,a_{n+1},c_1,..c_nが与えられるのでa_1を求めよ。

やりかた

(たぶん嘘解法)
a_1に対してa_{n+1}がmonotonicalに変化するからa_1に関して二分探索すればいいんじゃまいか(・∀・)!!
で通ってしまった。よく考えるとmonotonicalじゃないような。
実験すると一般項がわかるのでそれでやるのがいいと思う。

以下ソース。

//嘘解法っぽい
int n;
double b, a[3010];
double c[3010];
int main(int argc, char **argv){
  scanf("%d", &n);
  scanf("%lf", &a[0]);
  scanf("%lf", &b);
  for(int i = 1; i <= n; i++)
    scanf("%lf", c + i);
  
  double ub = 1001, lb = -1001;
  for(int i = 0; i < 100; i++){
   a[1] = (ub + lb) / 2;
   for(int i = 2; i <= n + 1; i++)
     a[i] = 2.0 * a[i - 1] - a[i - 2] + 2.0 * c[i - 1];
   if(b > a[n + 1]) lb = a[1];
   else ub = a[1];
  }
  printf("%.2lf\n", a[1]);
  return 0;
}
しょげないでよBaby 眠れば治る