Pの競プロ記

競技プログラミングに関することを書きます。

yukicoder No.53 : 悪の漸化式

概要

以下の漸化式が与えられるので、第N項ANを求めよ。

  • A0 = 4
  • A1 = 3
  • 4Ak = 19Ak-1 - 12Ak-2 (k > 1)

N≦100

http://yukicoder.me/problems/80

解法

結論から言うと、第N項は{ \displaystyle A_N=4(\frac{3}{4})^{N-1}}となるので、入力で与えられたNを代入してやればよい。

= = = = = = = = = =

今回のような三項間漸化式は以下のようなやり方で解くことができる。(高校数学なのに忘れかけていたので復習の意味も込めて)

{ \displaystyle A_{n+2}=pa_{n+1}+qa_n}
のような漸化式が与えられたとき、
{ \displaystyle x^2=px+q}
のような特性方程式を作り、その解α、βを求める。

これを利用して漸化式を
{ \displaystyle
A_{n+2}-\alpha A_{n+1}=\beta (A_{n+1}-\alpha A_{n}) \\
A_{n+2}-\beta A_{n+1}=\alpha (A_{n+1}-\beta A_{n}) \\
}
のような2通りに変形させる。

上記の変形した2式は公比α、βの等比数列なのでその一般項を求めることができる。そのときA2やA1の値を利用する。
これらの求めた2つの一般項の差を取ることでいい感じにAnを求めることができる。

今回の場合は、特性方程式を求めることで、α=4、β=3/4を得ることができる。
それらを漸化式の変形に当てはめてゴニョゴニョ計算してやると、解法の最初に記述した式を得ることができる。

ちなみにもっと簡単に漸化式を求めることができて、特性方程式の解をα、βとしたとき、漸化式の一般項は、
{ \displaystyle A_{n}=P\alpha ^n+Q\beta ^ n}
となり、P,Qを初期条件から求める。

というやり方もあり、このやり方のほうが簡単に求めることができる。

余談

上記解法でやる前に思考停止でBigDecimalを使って解いてしまったことを反省している。

ソースコード

#include <bits/stdc++.h>

#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define F first
#define S second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

int main() {
  // ios_base::sync_with_stdio(false);
  int N;
  cin >> N;
  printf("%.10f\n", 4 * pow(0.75, N));;
  return 0;
}