ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

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通りのどちらかに絞られます。

  1. 最大要素  M を使うと仮定したときに実現できる最大値。
  2.  \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) で解けます。

ACコード

Submission #56104187 - Codeforces