CodeIQ「『トライアングル・メイズ』問題」に参加しました。

CodeIQ「『トライアングル・メイズ』問題」の掲載期間が終了したということで、自分が提出したコード(Python3)を公開します。ほかの解答者のコードはTogetterにまとめらていますので、そちらもぜひ。

"""
「『トライアングル・メイズ』問題」の解答コード。

1. 漸化式はF(n + 1) = F(n) * (F(n) + 1)
2. F(n) mod 1000003, F(n + 1) mod 1000003, ... が「繰り返し」を持つことを利用する
"""

if __name__ == '__main__':
    ls = [0, 1]
    ht = {}

    # n=0からF(n)の値を探索しlsに記録する。
    # 「繰り返し」が現れた時点で探索を終了してもよい。
    for i in range(2, 10000003):
        t = (ls[-1] * ls[-1] + ls[-1]) % 1000003
        if t in ht: break

        ls.append(t)
        ht[t] = i
    
    # 「繰り返し」の開始地点と終了地点を探す
    start = ht[(ls[-1] * ls[-1] + ls[-1]) % 1000003]
    end = len(ls) - 1

    # F(n)の値を計算し、出力する。
    n = int(input())
    if end < n: n = (n - start) % (end + 1 - start) + start
    
    print(ls[n])

さて感想ですが、漸化式$F(n + 1) = F(n) * (F(n) + 1)$と「繰り返し」のふたつに気がつけば溶ける問題だったように思います。漸化式についてはシンプルで気が付きやすいものでしたし、サンプルに挙げられた値をGoogle検索すればOEISがヒットした記憶もあります(肝心のページは失念)。また「100003でわったあまりを求めなさい」という指示から「繰り返し」も連想しやすかったと思います。