Manthan, Codefest 16 D. Fibonacci-ish

問題

codeforces.com

解法

直前の 2 要素が 0 の時, またその時のみ数列のすべての値が 0 になります。

それ以外の場合は, 普通のフィボナッチ数列と同じように, 指数オーダーで発散します。調べてみると, 大体 100 個程度あれば絶対値が 10^9 を超えてきそうなので, (a[i] == 0 ^ a[j] == 0) を満たさないすべての (i, j) について, それらを初項にする数列を調べていけば良いです。

本番ではそれを調べるのに, unordered_map を使っていたんですが, unordered_map は find に最悪 O(n) かかるらしいので TLE します。辛いね。

unordered_map はvector> という構造をしていて, ハッシュ値が同じものは同じリストにどんどん追加されていくので find に最悪 O(n) かかるんですね。

ただまだ疑問なことがあって, vector の size はどうやって決めてるんでしょうねって問題が

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n);
    map<ll, int> mp;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        mp[a[i]]++;
    }
    int ans = mp[0];
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (i!=j) {
        if (a[i] == 0 && a[j] == 0) continue;
        vector<ll> V;
        V.push_back(a[i]);
        V.push_back(a[j]);
        mp[a[i]]--;
        mp[a[j]]--;
        while (1) {
            int len = V.size();
            ll v = V[len-1] + V[len-2];
            if (mp.find(v) == mp.end() || mp[v] == 0) {
                ans = max(ans, len);
                break;
            }
            mp[v]--;
            V.push_back(v);
        }
        for (ll el : V) mp[el]++;
    }
    cout << ans << endl;
    return 0;
}