始めに

そろそろ３か月間ブログを書かずにいるので、簡単に書ける内容として今回も競技プログラミングのメモを残そうと思います。

また、今回説明する問題はコンテスト中解くことが出来ずにイライラしてその憂さ晴らしも兼ねております。

ABC170 D Not Divisible

問題はとても単純です。

長さ N の数列 A が与えられます。
次の性質を満たす整数 i(1≤i≤N) の数を答えてください。

i≠j である任意の整数 j(1≤j≤N) についてAiはAjで割り切れない

入力例１では

5
24 11 8 3 16

となっており、この中で3, 8, 11が他の整数で割り切れないため答えは 3 となります。

入力例２では

4
5 5 5 5

となっており、どの整数をとっても他の整数で割ることが出来るので答えは 0 となります。

この問題が解けそうでずっと解けませんでした。
私が提出したコードでは割り切れなかった数をvectorに保存して、そのvectorを使用して整数が割り切れるかどうかを確かめていました。

以下、私がコンテスト中に提出したプログラムです。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main() {

    int n;

    cin >> n;

    vector<int> v(n);
    vector<int> ans;

    for(int i = 0; i < n; ++i)
        cin >> v[i];

    sort(v.begin(), v.end());

    int count = 0;

    for(int i = 0; i < n; ++i) {

        
        int j;
        for(j = 0; j < ans.size(); ++j) {

            if(v[i] % ans[j] == 0 || v[i] / ans[j] < 1)
                break;

        }

        if(j == ans.size()) {
            ans.push_back(v[i]);
            count++;
            if(i + 1 < n && v[i] == v[i + 1])
                count--;
        }

    }

    cout << count << endl;

    return 0;

}

このプログラムではvectorに保存された整数分だけループが行われるので、感覚的にはなりますがO(N²)となると思います。

解法

コンテスト終了後、twitterで情報収集を行ったところエラトステネスの篩という単語を見つけました。ちなみに篩と書いてふるいと読むそうです。

このアルゴリズムでは素数、素数でない数を一気に求めることが出来ます。

例えば 1 ~ 10 の整数があるとします。 f:id:vxd-naoshi-19961205-maro:20200615000546p:plain

この中の最小の素数は2です。ここから2以外の2の倍数を素数ではない数として登録します。 f:id:vxd-naoshi-19961205-maro:20200615001003p:plain

次に 3 も素数となっているので、同様に3以外の3の倍数を素数ではない数として登録します。 f:id:vxd-naoshi-19961205-maro:20200615001232p:plain

次に４を見ますが、これは素数ではないとなっているので、スキップします。次に５ですが、これは素数となっているので2, 3と同じ処理をして5以外の5の倍数を素数ではないとしていきます。

このアルゴリズムはwikipediaのサイトにとても見やすいgif付で解説されているので参考になると思います。(https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9)

ちょっと解説が長くなりました。これから問題の解説に移りたいと思います。このエラトステネスの篩のようなアルゴリズムを使用します。

以下コンテスト後に提出したプログラムになります。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {

    int n;

    cin >> n;

    vector<int> v(n);

    for(int i = 0; i < n; ++i)
        cin >> v[i];

    sort(v.begin(), v.end());
    int maxV = v[n - 1];

    vector<bool> used(maxV + 1, false);
    int count = 0;

    for(int i = 0; i < n; ++i) {

        if(used[v[i]])
            continue;

        for(int j = 1; j * v[i] <= maxV; j++) {
            used[v[i] * j] = true;
        }

        if(i + 1 < n && v[i] == v[i + 1])
            continue;

        count++;

    }

    cout << count << endl;

    return 0;

}

始めにこの問題は数列の順番は関係ないので、昇順にソートします。

    sort(v.begin(), v.end());

次に、表を作ります。表の最大値はソートされた数列の最後尾の値の数になります。

   int maxV = v[n - 1];

   vector<bool> used(maxV + 1, false);

この表を使用してある数列の値が他の値で割り切れるかを確かめていきます。

まず、ある要素が表で他の値で割り切れるかを確かめます。そうである場合は次に要素に進みます。

そうでない場合は、その要素の値以外の倍数を表に登録していきます。

  for(int i = 0; i < n; ++i) {

        if(used[v[i]])
            continue;

        for(int j = 1; j * v[i] <= maxV; j++) {
            used[v[i] * j] = true;
        }

        if(i + 1 < n && v[i] == v[i + 1])
            continue;

        count++;

    }

ちなみに、他の値と割り切れない数の個数を求めたい場合同じ数があると余分に数えてしまいます。

そこで、数列のある要素を見ている際に次の要素と同じ場合は個数を数えないようにしています。

        if(i + 1 < n && v[i] == v[i + 1])
            continue;

このプログラムでACすることが出来ました。

感想

このアルゴリズムはプログラムを学んだ初期のころに一度だけ書いたことがありましたが、いざ実際に問題に直面した時に思いつくことが出来ませんでした。

なので、もっと経験値を貯めていきたいです。

p.s. そろそろUnity記事書きます。

したかみぶろぐ

Unity成分多め

ABC170 D Not Divisible

始めに

ABC170 D Not Divisible

解法

感想