ABC170 D Not Divisible

はじめに

　本記事は競技プログラミングにおいて解くのに困った問題について、なぜその解法に思い至るのか、どのような所でハマったか等のポイントをメモした、筆者の筆者による筆者のための備忘録となっております。読まれることを意識していないので文章がとっ散らかってます。

問題

問題はこちら。

問題文
長さ$N$の数列$A$が与えられます。
次の性質を満たす整数$i(1\leq i \leq n)$を答えてください。

• $i \neq j$である任意の整数$j(1 \leq j \leq N)$について$A_i$は$A_j$で割り切れない

制約

• 入力はすべて整数
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^6 $

提出解答

解答はこちら。

ABC170D.py

n = int(input())
a = list(map(int, input().split()))
a.sort()
a_max = max(a)
dp = [True]*(a_max+1)
for i in range(n):
    for j in range(2*a[i], a_max+1, a[i]):
        dp[j] = False

ret = 0
for i in range(n):
    if (i < n-1 and a[i+1]==a[i]) or (i > 0 and a[i-1]==a[i]):
        continue
    if dp[a[i]]:
        ret += 1

print(ret)

エラトステネスの篩(ふるい)

　これはある自然数$N$以下の素数を求めるアルゴリズムです。詳しくはこちらやこちら。
　ざっくりと手順を書くと、

1. $2,...,N$の自然数列$A$と、空の数列$P$を用意する。
2. $A$に含まれる最小の要素$p$を数列$P$に追加し、$A$から$p$の倍数をすべて取り除く。
3. $p$が$\sqrt　N$を超えたところで終了。$P \cup A$が$N$以下の素数。

となります。考え方の根底には、「自然数から倍数を除いて残ったものを求めよう」というものが見られます。ちなみに2021 年度の一橋大学入学試験の数学において、これを背景とした問題が出題され、話題になりましたね。

なんでこの解法に至る？

　元の問題に戻りましょう。まず、愚直な計算でやると計算量は如何ほどになるかを考えてみます。
　各$i(1 \leq i \leq N)$に対して$i \neq j$ なる$j$は$N-1$個ありますから、各$i, j$の組について判定していくと、計算量は$N(N-1)$で$O(N^2)$となり、今回の制約下ではTLEしてしまいます。困っちゃいました。
　そこで「$A_i$は$A_j$で割り切れる」という文章を「$A_i$は$A_j$の倍数である」と読み替えてみます。すると、

• $A$をソートしておいて、各$i$について$2A_i, 3A_i, ...$を$A$から除いていき、残ったものの個数が答え

というような考えに至ります(これは厳密には正しくないことが後ほどわかりますが、大体の方針は上記の通り)。これはまさに先ほど述べたエラトステネスの篩の考え方と合致します。ここで$A_i$自身は除く必要がないことに気を付けましょう。
　ただ、「$x$を$A$から除く」という操作はちょっとやりにくいので、別の方法をとりましょう。すなわち、長さ$A_{max}$のbool値を持つ列$B$を用意し、すべてTrueで初期化しておきます。この下で、

• $A$をソートしておいて、各$i$について$B_{2A_i}, B_{3A_i}, ...$をFalseにしていく。
• $x \in A$のうち、$B_x$ = Trueなるものの個数が答え。

と言えるでしょう。
　一つ目の手順は計算量$O(A_{max}\log A_{max})$、二つ目の手順は計算量$O(N)$で完了でき(計算量は適当なので間違っているかも)、本問の制約下で解くことができます。

本当にこれでいいのか？

　これで万事解決......としたいところでしたが、何やらテストケースに不穏な一文が。

「同じ数が存在する場合に注意してください。」

......怖いです。実際上の解法をこのテストケースである$A=[5, 5, 5, 5]$について適用してみましょう。

• $A_1 = 5$なので5以外の5の倍数をAから除きたいが、それは存在しないのでスキップ。
• $A_2, A_3, A_4$についても同様。
• $A=[5, 5, 5, 5]$が生き残り、答え$4$。

おかしくなっちゃいました。それもそのはずで、エラトステネスの篩の考え方は元々対象が自然数の列でしたから、対象となる数列が同一の要素を持たない時にうまくいくもので、要素の重複があるときのことは考慮されていないわけです。
　しかし途方に暮れる必要はありません。重複した要素は、互いに割り割られることができるわけですから、条件を満たしようがないわけです。ゆえに前項の手順に以下の文言を付け加えたものが、最終的な計算プロセスになります。

• $x \in A$のうち、$A$に複数個存在する要素は無視する。

これで無事解くことができました。わいわい。

反省

　以下は個人的な反省です。

• 「割り切れる→倍数である」の読み替えは思いついたが、そこから具体的な解法に至らなかった。「約数が存在しない→エラトステネスの応用」に思い至れるとよかった。
• $A$に要素が複数個存在するか否かの判定について、ソートしていたため前後に同一要素があるか否かで判定したが、Counterを使えるとよかった。便利なライブラリは覚えていきたい。