yukicoder No.1268 - Fruit Rush 2

No.1268 Fruit Rush 2 - yukicoder

問題

フィボナッチ数列 $(F_i)$ を以下のように定める。

$F_0 = F_1 = 1$
$F_i = F_{i-1} + F_{i-2} \quad (i \geq 2)$

また $(F_i)$ に出現する整数をフィボナッチ数ということにする。

全ての要素が異なる長さ $N$ の正整数列 $(A_i)$ が与えられる。 $S \subseteq \{1, \cdots, N\}$ で以下を満たすものの個数を求めよ。

$S \neq \emptyset$
$\sum_{i \in S} F_{A_i}$ がフィボナッチ数である。

制約

$1 \leq N \leq 2 \cdot 10^5$
$1 \leq A_i \leq 10^{18}$
$i \neq j \implies A_i \neq A_j$

考察

総和が $F_k$ になるような選び方を数え上げる。まず考えられるのは $k = A_i$ なる $i$ を選ぶ方法で、このとき他のものは選べないので高々 1 通り。

そうでない場合、実は $F_{k-1}$ を必ず選ばなくてはならない。これは $F_{k} \gt \sum_{i=1}^{k-2} F_i$ が成り立つことから従う(証明は帰納法)。 $F_{k-1}$ を選んだ後は、 $F_k - F_{k-1} = F_{k-2}$ より総和が $F_{k-2}$ になる選び方の数え上げに帰着される。

以上の考察から、 $k$ として考えるべきなのは $\bigcup_{i} \{ A_i, A_i + 1 \}$ の元に限定されることが分かる。後は set や map を使うことで、上の場合分けをそのままシミュレートすることができる。

実装例

#570750 (C++17) No.1268 Fruit Rush 2 - yukicoder

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


#include <iostream>
#include <set>
#include <map>

using lint = long long;

void solve() {
    int n;
    std::cin >> n;

    std::set<lint> xs, ks;
    while (n--) {
        lint x;
        std::cin >> x;

        xs.insert(x);
        ks.insert(x);
        ks.insert(x + 1);
    }

    lint ans = 0;
    std::map<lint, lint> dp;  // sumがF_kになる選び方の総数

    for (auto k : ks) {
        auto& pat = dp[k];
        pat = 0;

        // F_k単体
        if (xs.count(k)) ++pat;

        // F_{k-1}を使いF_{k-2}に帰着
        if (xs.count(k - 1) &&
            dp.count(k - 2)) pat += dp[k - 2];

        ans += pat;
    }

    std::cout << ans << "\n";
}