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

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

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

数列をヒストグラム化することで解決できるタイプの問題!特に今回みたいに、数値の値も  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;
}