数列をヒストグラム化することで解決できるタイプの問題！特に今回みたいに、数値の値も $10^{6}$ 以下と小さい場合はすごくそれっぽい！

問題へのリンク

問題概要

長さが $N$ の正の整数からなる数列 $A_{1}, \dots, A_{N}$ が与えられる。以下の条件を満たす $i$ の個数を求めよ。

$j \neq i$ なる任意の $j$ に対して、 $A_{i}$ は $A_{j}$ の倍数ではない

制約

$1 \le N \le 2 \times 10^{5}$
$1 \le A_{i} \le 10^{6}$

考えたこと

数列 $A$ を次のような配列に変換して考えるのは、割とよくやっても良さそうな気がする。

num[v] ← 数列 $A$ の中に $v$ が何個あるか

このように変換したとき、サイズ $N$ に関する問題から、サイズ $V$ に関する問題へと変わる ( $V$ を登場する最大値とする)。このように変換してあげた方が解きやすいことも多い。

さて、今回の問題を解くにあたっては、エラトステネスの篩と同じような方法でやると良さそう。こんな感じ。

int V = 1000000;
vector<bool> ok(V, true);
for (int d = 1; d < MAX; ++d) {
     if (v[d] == 0) continue;
     if (v[d] > 1) v[d] = 0;
  
     // d の倍数を除去していく
     for (int e = d * 2; e < MAX; e += d) v[e] = 0;
}

これは一見すると $O(V^{2})$ かかるように見えるかもしれない。しかしちゃんと解析すると $O(V \log V)$ になっているのだ。計算時間をよりちゃんと書くと

$\frac{V}{1} + \frac{V}{2} + \dots + \frac{V}{V}$

という風になる。二番目の for 文は $d$ の倍数のみを走るので、大体 $\frac{V}{i}$ くらいの範囲を動くことになるのだ。一方

$1 + \frac{1}{2} + \frac{1}{3} + \dots = O(\log N)$

となることが知られている ( $\frac{1}{x}$ の積分が $\log x$ であることから来る)。よって、上述の処理の計算量は $O(V \log V)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

const int MAX = 2100000;

int main() {
    int N;
    cin >> N;
    vector<long long> v(MAX, 0);
    for (int i = 0; i < N; ++i) {
        long long a;
        cin >> a;
        v[a]++;
    }
    for (int d = 1; d < MAX; ++d) {
        if (v[d] == 0) continue;
        if (v[d] > 1) v[d] = 0;
        for (int e = d * 2; e < MAX; e += d) v[e] = 0;
    }
    long long res = 0;
    for (int d = 1; d < MAX; ++d) res += v[d];
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 170 D - Not Divisible (緑色, 400 点)

問題概要

制約

考えたこと

コード