独力で方程式の導出が出来た

UVa Online Judgeの!! Really Strange !!を解いた。

独力で方程式を導出できた。うれしいので解説を書く。

まず、問題文からは
f(n) = 2(n-1) + f(n-1)
というnに関する漸化式が作れる。ここに、f(1) = 2
問題のサイズnが小さければ、この漸化式を元にした再帰関数を使うことで答えを求めることができるが、今回は最大サイズが10^100と巨大なので、再帰を使ったら時間制限に多分引っかかる。

そこで、方程式を導出できないかと考えてみたらできた。式の変形を書く。
f(n) = 2(n-1) + f(n-1)
= 2(n-1) + (2(n-2) + f(n-2))
= 2(n-1) + (2(n-2) + (2(n-3) + f(n-3))
= ...
= 2(n-1) + 2(n-2) + 2(n-3) + ... + 2(n-(n-1)) + f(1)
= 2(n(n-1) - 1/2(n-1)n) + 2
= 2(1/2n(n-1)) + 2
= n(n-1) + 2
= n^2 - n + 2

ということで、
f(n) = n^2 - n + 2
となることが分かった.

確認のために、3,4,5の場合の値を計算してみると、
f(3) = 9 - 3 + 2 = 8
f(4) = 16 - 4 + 2 = 14
f(5) = 25 - 5 + 2 = 22
と正しい値が得られている。