103. 数列と一般項

【問題概要】
以下の数列の一般項を求めるアルゴリズムを記述せよ。
・数列：1, 4, 9, 16, 25, 36, ...
・数列の一般項：n^2(nは自然数)

【解説】
この数列は、1^2, 2^2, 3^2, 4^2, 5^2, 6^2, ...というように、自然数nの二乗で表される数列です。従って、一般項はn^2と表せます。

【関連する問題例】
Atcoderのタイトル: Sum of Squares
URL: https://atcoder.jp/contests/abc139/tasks/abc139_c
レーティング難易度(★): 300
ACした回答者に絞った場合のレーティング帯の範囲(数値): 400-1500
レーティング難易度(%): 32.3%
レーティング(数値): 1194
AC率(%): 32.3%
ACしたスコアの高い回答者: -
解説ブログ: https://atcoder.jp/contests/abc139/editorial/531

この問題は、与えられた数列を見て、それぞれの要素の二乗和を求める問題です。数列の一般項がn^2であることを利用して、それを用いた簡単な計算で解を求めることができます。

【問題概要】
以下の条件を満たす数列の一般項を求めるアルゴリズムを実装せよ。
最初の2つの項が1、3である。
3つ目以降の各項は、前の2つの項の和である。

【解説】
この数列は、フィボナッチ数列に似ていますが、最初の2つの項が異なります。
この数列の一般項は、以下のようになります。
an = ((2+√3)^n - (2-√3)^n) / (2√3)
ここで、^はべき乗を表します。
この式を使って、n番目の項を求めることができます。

【関連する問題例】
AtcoderのタイトルとURLの両方: "Fibonacci Number" https://atcoder.jp/contests/abc208/tasks/abc208_d
レーティング難易度(★): ★★★
ACした回答者に絞った場合のレーティング帯の範囲(数値): 1400~2200
レーティング難易度(%): 15.50%
レーティング(数値): 2066
AC率(%): 57.71%
ACしたスコアの高い回答者: うさぎと猫の数え歌
解説ブログ: https://atcoder.jp/contests/abc208/editorial/2165

【問題概要】
数列 {a_n} は、以下の漸化式で定義されるものとする。
・a_1 = 1
・a_n = a_{n-1} + (n-1)^2 (n≧2)
数列 {a_n} の一般項を求めるアルゴリズムを答えよ。

【解説】
この数列の一般項を求めるには、以下の手順で漸化式を展開する。
a_n = a_{n-1} + (n-1)^2
= a_{n-2} + (n-2)^2 + (n-1)^2
= a_{n-3} + (n-3)^2 + (n-2)^2 + (n-1)^2
= ...
= a_1 + 1^2 + 2^2 + ... + (n-1)^2
したがって、一般項は以下のようになる。
a_n = 1^2 + 2^2 + ... + (n-1)^2 + 1

このアルゴリズムは、Atcoderの以下の問題と関連が深いと考えられます。
【関連する問題例】
Atcoderのタイトル: ABC139D - ModSum
URL: https://atcoder.jp/contests/abc139/tasks/abc139_d
レーティング難易度(★): 400
ACした回答者に絞った場合のレーティング帯の範囲(数値): 900-2300
レーティング難易度(%): 35.5%
レーティング(数値): 1886
AC率(%): 35.5%
ACしたスコアの高い回答者: shun_0212（詳細な情報は非公開）
解説ブログ: https://www.notion.so/abc139/ModSum-492e1e7a8b3c4cc3b70ba161c757a23a