SECON 2017 Online CTF Run me!(Programming, 100pt)

問題文

Run me!
-----  RunMe.py
import sys
sys.setrecursionlimit(99999)
def f(n):
    return n if n < 2 else f(n-2) + f(n-1)
print "SECCON{" + str(f(11011))[:32] + "}"
-----

11011番目のフィボナッチ数列を計算するプログラムですが、再帰なので自明にスタックオーバーフローします。
なので、動的計画法で書き直します。

import sys
sys.setrecursionlimit(99999)

fib = [0] * 99999
fib[1] = 1
fib[2] = 1
for i in range(3, 11111):
    fib[i] = fib[i-1] + fib[i-2]
print "SECCON{" + str(fib[11011])[:32] + "}"

これで実行できました。
一時変数を全部配列で持ってしまっていますが、本来はラスト2つだけ持てば十分ですね。

感想

完全に競技プログラミング系の問題ですね。
こういうのも出るのか、、、と思いました。