E - Self-contained

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

問題

0以上未満の整数からなる集合が与えられる。この中の相異なる3要素で、となるものはあるか。

知識

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

解法

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

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

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

そのような組み合わせが存在するとしたら、はのいずれかとなっているはずです。

そこでを考えます。

もしもの組み合わせの中で、実際に集合の要素で構築可能なものがあったとしたらは1以上になります。逆にそのようなものがなかったとしたらsumのすべての項は0となります。

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

このアルゴリズムの計算量はです。