ABC 401-500/ABC427F - Not Adjacent - 競技プログラミング用 知識集積所

---

問題

ABC427F

必要知識

B以下レベルの内容は省略

• 半分全列挙※
• 動的計画法、または、Zeckendorf全探索※

考え方

まず、bit全探索※では2^60通りを確認しなければならず、全く間に合わない。
そこで半分全列挙※を考えるのだが、これでも単純にbit全探索※をすると、2^30通りでやはり間に合わない。

そこで、視点を変える。
隣接しない項をいくつか選ぶ方法は、フィボナッチ数で表せる。
これなら30項で200万ちょっとで済むので、bit全探索※から無駄を省いて効率的に作れば半分全列挙※は間に合いそうということになる。

これにはいくつか方法がある。

一番わかりやすいのは、端から順に項を1つずつ追加しながら、「その項を使う和」と「その項を使わない和の一覧」を動的計画法で更新していく方法。
1つ追加するごとに、

• 1つ前を使わないもの全部に、新しく追加した数を足して「その項を使う和」予定にする（どこかに退避しておく）
• 1つ前を使うもの全部を、「その項を使わない和の一覧」に追加する
• 退避データを使って、「その項を使う和」を更新する

を繰り返せばよい。

少しトリッキーな方法としては、Zeckendorf全探索※もできる。
Zeckendorfの定理は、いくつかの一列に並んだものから隣接なしでデータを選ぶ方法を、0以上の連続する整数と対応付けることができる。
したがって、bit全探索※と似たような方法で連続して選ぶことがない和の取り方だけを効率よく計算することができる。

また、結果の持ち方も、2通りある。
vectorに全部入れてもよいし、map※で個数管理をしてもよい。

いずれにせよ、半分全列挙※ができたら、結果の結合をする。
しかし、ここで結合部のギリギリにある数値を左右両方使うことができないことに注意が必要。
中心付近のc番目で結合するとして、ここでも2通りのやり方がある。

1つめは、
「左側はc-1番目を使う+右側はc番目を使わない」
「左側はc-1番目を使わない+右側はc番目を使わない」
「左側はc-1番目を使わない+右側はc番目を使う」
の3つにわけて加算する方法。
ただし、これは最後の1つを使うか使わないかで分けてデータを持つ必要がある。

2つめは、c番目は特殊な扱いとして、
「左側はc-1番目までのデータ、c番目は使わず、右側はc+1番目からのデータ」
「左側はc-2番目までのデータ、c番目は使って、右側はc+2番目からのデータ」
を加算する方法。
ただし、これは左右それぞれ2つの異なる範囲のデータを用意する必要がある。
また、そもそものデータ数が少ない場合に特殊なケアが必要。

いずれにせよ、データの結合を何回かやり、答えの合計を取ればいい。
結合自体は、vector管理の場合は片方をソートしておいて二分探索※で、map※の場合は該当する組み合わせのパターン数の積を足していけばいい。

解答例

解答例（端から順に1つずつ追加、map※で個数管理、端を使うか使わないかで調べる）
解答例（Zeckendorf全探索、vectorをソートして二分探索※、c番目は特殊な扱い）

注意点

和が0のケースを忘れずに。

半分全列挙※時に、何も拾わないときの0を数え忘れてはいけない。

答えにはlong long型を使うこと。

全部0の場合にはどう選んでも倍数ができる、みたいな場合に答えがint型に収まらない場合がある。

別解