mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ CodeForces 問題 codeforces.com 解法 直前の 2 要素が 0 の時, またその時のみ数列のすべての値が 0 になります。それ以外の場合は, 普通のフィボナッチ数列と同じように, 指数オーダーで発散します。調べてみると, 大体 100 個程度あれば絶対値が 10^9 を超えてきそうなので, (a[i] == 0 ^ a[j] == 0) を満たさないすべての (i, j) について, それらを初項にする数列を調べていけば良いです。本番ではそれを調べるのに, unordered_map を使っていたんですが, unordered_map は find に最悪 O(n) かかるらしいので TLE… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2016%2F02%2F27%2F203605" title="Manthan, Codefest 16 D. Fibonacci-ish - mayoko’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2016-02-27 20:36:05 rich https://mayokoex.hatenablog.com/entry/2016/02/27/203605 1.0 100%