E - Self-contained

原題はE - Self-containedですが、問題の本質は以下のとおりです。

問題

0以上 n \ (0 \lt n \le 500000)未満の整数からなる集合が与えられる。この中の相異なる3要素 (a, b, c)で、 a + b = cとなるものはあるか。

知識

今回は要素の大きさに制限がありますが、制限がない場合、 O(n^2)アルゴリズムが限界だと思われているようです。2018年度の東京大学情報理工学系研究科コンピュータ科学専攻の院試に似たような話がありました。

解法

まず、話をわかりやすくするために配列 a[500000]を定義します。 a[i]は整数 iが集合に含まれるとき1, そうでないとき0とします。

さて、集合の中の相異なる2要素 a, bを考えたときに、これらの和は999999未満となりますね。

では、和が mとなるような a, bの組み合わせを考えてみましょう。

そのような組み合わせが存在するとしたら、 (a, b) (0, m), (1, m - 1), \ldots, (m, 0)のいずれかとなっているはずです。

そこで \sum_{i = 0}^m a[i]a[m - i]を考えます。

もしも (0, m), (1, m - 1), \ldots, (m, 0)の組み合わせの中で、実際に集合の要素で構築可能なものがあったとしたら \sum_{i = 0}^m a[i]a[m - i]は1以上になります。逆にそのようなものがなかったとしたらsumのすべての項は0となります。

すでにピンときた方は多いでしょうが、これは離散フーリエ変換そのものです。 具体的には a[500000] a[500000]を畳み込んで得られる長さ 999999の配列のうち、前 500000個を新たに b[500000]と呼ぶことにすると、 a[500000], b[500000]のelementwise ANDがすべて0ならば、問題の条件を満たすtripletが存在しなく、1以上になるものがあれば存在します。

このアルゴリズムの計算量は O(n\log n)です。