Codeforces Round #570 (Div. 3) F. Topforces Strikes Back

ちょっと変わった解き方をしたので記録。

Problem - F - Codeforces

（追記）公式Editorial もこの解き方でした。

問題概要

以下の問題を $q$ ケース解け。

$n$ 個の正整数 $a_{1}, ..., a_{n}$ が与えられる。この中から3個以下の整数を「どの2要素も約数・倍数の関係にない」という条件を満たすように選んだ時の、合計値の最大値を求めよ。

制約

$1 \le q \le 2\times 10^{5}$
各ケースについて、
- $1 \le n \le 2\times 10^{5}$
- $2 \le a_{i} \le 2\times 10^{5}$
全ケースの $n$ の合計は $2\times 10^{5}$ 以下

解法

「どの2要素も約数・倍数の関係にない」ことを単に「条件を満たす」と書くことにします。

同じ整数を2個以上選ぶことはできないので、とりあえず重複要素を除いておきます。以降は全要素が異なっているとします。

貪欲で行けないか？

$O(n^{2})$ 以上の解法は通りそうになく、DPを組むのも難しそうなので、貪欲を疑ってみます。大きい方の要素から決められると嬉しいので、試しに「一番大きい要素を取ると決めてしまって良いだろうか？」「もしそれがダメなら、どのような反例が考えられるか？」を考えてみましょう。

これを証明するための常套手段は、

一番大きい要素を $M$ として、 $M$ 以外から3個以下の要素を条件を満たすように選んだとき、ここから $M$ を選ぶように変更することで値を改善できる

ことを示すことです。

実際に、ほとんどの場合では値を改善できると示すことができます。選んだ要素の中に $M$ の約数が何個含まれるかで場合分けします。

$M$ の約数が0個の場合

この場合、どれか1個の要素を選ばないことにして代わりに $M$ を選ぶことで値が改善します。どれも $M$ の約数でないので条件に違反することはありません。

$M$ の約数が1, 2個の場合

この場合、 $M$ の約数であるものを選ばないことにして代わりに $M$ を選ぶと、条件に違反せずに必ず値が改善します。なぜなら $M$ の約数で $M$ でないものは $\frac{M}{2}, \frac{M}{3}, \frac{M}{4}, ...$ のいずれかであり、この中から1個または2個を選んだ和は必ず $M$ よりも小さくなるからです。

$M$ の約数が3個の場合

同様に「 $M$ の約数を全部外して代わりに $M$ を選ぶと値が改善する」と言いたいところですが、3個ある場合は少しだけ事情が違います。3個の和が $M$ を超えるものが1パターンだけ存在し、それは $\frac{M}{2} + \frac{M}{3} + \frac{M}{5} = \frac{31}{30}M$ の3個を選んでいる場合です。これは親切にサンプルにも含まれています。

これ以外に和が $M$ を超えるパターンがないことを示します。先ほどと同様に、 $M$ の約数で $M$ でないものは $\frac{M}{2}, \frac{M}{3}, \frac{M}{4}, ...$ のいずれかであることを使います。

まず、3個全てが $\frac{M}{3}$ 以下だと和が $M$ を超えられないので、 $\frac{M}{2}$ は必ず含まれている必要があります。そうすると $\frac{M}{2}$ の約数となる $\frac{M}{4}, \frac{M}{6}, \frac{M}{8}, ...$ は採用できません。

あと2個で残りの $\frac{M}{2}$ を超える必要があるので、同様の理由で $\frac{M}{3}$ が必ず含まれる必要があります。そうなると最後の1個はどちらの約数でもない $\frac{M}{5}, \frac{M}{7}, \frac{M}{11}, ...$ から選ぶ必要があり、 $\frac{M}{2} + \frac{M}{3} + \frac{M}{7} = \frac{41}{42}M \lt M$ であることから、最後の1個は $\frac{M}{5}$ しかありえません。

以上の考察を踏まえて

つまり、答えは以下の2通りのどちらかに絞られます。

最大要素 $M$ を使うと仮定したときに実現できる最大値。
$\frac{M}{2}, \frac{M}{3}, \frac{M}{5}$ が全て含まれている時に限り、これら3個を選んだ合計値 $\frac{31}{30}M$ 。

最大要素を使うと仮定すれば、あとは $M$ の約数を全て消した上で、約数・倍数関係でない残り2個の合計を最大化する問題になります。これは先ほどの「 $M$ の約数が2個以下」のときの議論がそのまま使えて、やはり選べるものの中で最大のものを2個目として選ぶのが最適となります。さらに残ったものの中から3個目を選べば良いので、結局3個とも大きい方から貪欲で選べます。

$\frac{M}{2}, \frac{M}{3}, \frac{M}{5}$ が全て存在する場合は貪欲解と $\frac{31}{30}M$ の大きい方を採用し、存在しない場合は貪欲解をそのまま答えとすれば良いです。ソートやsetの利用などを考慮して、ケースごとに計算量 $O(n\log n)$ で解けます。