東京海上日動プロコン（ARC122） A - Many Formulae

　公式解説の解法とわたしがコンテスト中に思いついた解法が違ったので、解説をしてみます。たぶん、嘘解法ではなさそうです。

　一応、解法は丁寧に解説しているつもりですが、お急ぎの方もいらっしゃるかと思い、最後の方に "解法まとめ" として、簡単に解法を書きましたので、そちらをご覧いただくだけでもかまいません。

問題
重要な事実
解法
解法まとめ
AC コード
最後に

問題

atcoder.jp

これをご覧ください

重要な事実

　結論から言えば、私はコンテスト中にフィボナッチ数を用いた解法で通しました。フィボナッチ数には、この問題にかかわる次のような重要な事実があります：

　'A' と 'B' を合計で ${n}$ 個、横一列に並べる。この時、'B' が隣り合わないように並べる方法は $F_{n+2}$ 通りある。（ $F_n =$ フィボナッチ数列の第 $n$ 項）

　なぜそうなるか、を証明した論文みたいなのはちょっと調べてないんですが（おい）、まあそうなるっぽいです。

解法

　では、本題の方に移っていきましょう。

　まず、作る式に項は $N$ 個あります。つまり、並べる符号の数は、合計で $N - 1$ 個ですので、作ることができる良い式は全部で $F_{(N-1) + 2} = F_{N + 1}$ 通りです。なので、 $S = A_1 + A_2 + \cdots + A_N$ として、 $\mathrm{sum} = F_{N + 1} \times S$ という値で初期化しておきます。（ $F_i$ の値は、ちゃんと $\mathrm{mod}\ 10^9 + 7$ の値をとっておきます）

　ここでは、 $F_1 = 1, F_2 = 2, F_n = F_{n-2} + F_{n-1} (n \geq 3)$ であるとします。

　ここからどんな操作をしていくかというと、各項の値を、ある分だけ $\mathrm{sum}$ から引いていくという操作を全ての $A_i (1 \leq i \leq N)$ に対して行っていきます。とはいっても、 $A_1$ の符号は正から変えられないので、ここに対しては特に操作をする必要はありません。

　ある分だけ引く、とはどういうことかというと、 $A_i$ の符号を負にした時に作れる良い式を $P_i$ としたとき、 $2 P_i$ 回だけ $A_i$ を $\mathrm{sum}$ から引くということです。

　なぜこの回数引くかというと、最終的にはありうるすべての良い式を足し合わせるわけで、そうすると各項の和は、次のように表されるからです： $\displaystyle \sum_{i=0}^N \{(F_{N + 1} - P_i) \times A_i - P_i \times A_i \}$

　これを式変形すれば、 $\displaystyle \sum_{i=0}^N (F_{N + 1} - 2 P_i) \times A_i$ となりますから、先ほどの回数だけ引くことが正しいと言えます。

　さて、あとはこの $P_i$ の値が求まればいいわけですが、これは、先ほどのフィボナッチ数の性質を使えば、 $P_i$ の値は $O(1)$ で求められます。

　次のように、6 個の項の、3 番目の演算子が '-' になった場合を考えてみましょう。

f:id:kanten4205:20210616213308j:plain

　赤の部分は演算子が '+' が確定しますが、青の部分は演算子が確定しません。この時、良い式は何通り作れるでしょうか。

　正解は、4 通りです。当てはめてみれば、それはそうなんですが、左側の青の部分は演算子が 1 つ、右側の青の部分は演算子が 1 つ入るので、それぞれ演算子の入れ方は $F_{1+2} = F_3$ 通りずつになります。 $F_3 = 2$ ですから、良い式は $F_3 \times F_3 = 2 \times 2 = 4$ より、4 通り作れる！となるわけです。

　一般化してみましょう。第 $n$ 項の符号を負にした時、上で言う左側の青の部分は、 $\mathrm{max} (n - 3, 0)$ 個の演算子を並べることになります。そして、上で言う右側の青の部分は、 $\mathrm{max} (N - n - 1, 0)$ 個の演算子を並べることになります。ですから、 $P_n = F_{n - 1} \times F_{N - n + 1}$ という計算をすればいいことになります。フィボナッチ数を前計算しておけば、各 $P_n$ は、 $O(1)$ で求めることができます。

　結果として、全体で $O(N)$ でこの問題を解くことができました。

解法まとめ

フィボナッチ数を、 $F_1 = 1, F_2 = 2, F_n = F_{n-2} + F_{n-1} (n \geq 3)$ として前計算しておく。
各 $A_i$ の値の総和と $F_{N + 1}$ の積の値で、 $\mathrm{sum}$ を初期化する。
$2 \leq i \leq N$ の各 $i$ について、 $P_i = F_{i - 1} \times F_{N - i + 1}$ を計算し、 $\mathrm{sum}$ から、 $2 \times P_i \times A_i$ を引く。
3. を全ての $i$ について行った後の $\mathrm{sum}$ の値が、求める値である。