ABC170に参加してみた

初めに

ABC170はABC完でした。D問題も解けそうな感じではあったんですが、
実装が間に合わず解けませんでした。CでWAを出してしまった影響か
レーティングも+2しかあがらずぐんにょりって感じでした。
今回はD問題について書いて行きます!

https://atcoder.jp/contests/abc170

※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。

D - Not Divisible

この問題は与えられたN個の数字のうち、ある数字を選択し、
選択した数字を残りの数字でそれぞれ割り算を行い、
選択した数字以外では割り切れないような数字の個数を集計します。

解説を見てからの回答
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const long long INF = 1LL<<60;

typedef pair<ll,ll> Pair;

int main(){

ll N;

//Aの取りうる最大値(10^6)分の配列を確保します。
vector<ll> H(1e6,0);

cin >> N;

vector<ll> A(N);

for(ll i = 0;i < N;++i) cin >> A[i];

for(ll i : A){
    // すでにふるい落ちている(1以上)場合はカウントをして、ふるいにかける処理をスキップします。
    if(H[i] >= 1){
         H[i]++;
         continue;
    }

  //ふるい落とされた各整数の倍数をカウント
    for(ll j = i;j <= H.size();j+=i)    H[j]++;     
}

ll ans = 0;

for(ll i = 0;i <A.size();++i) if(H[A[i]] == 1) ans++;

cout << ans << endl;

return 0;

}

この問題は素数判定で利用されるエラトステネスの篩と同じ処理を行うことで、
回答を導くことが出来ます。

エラトステネスのふるいとその計算量 | 高校数学の美しい物語

今回は与えられたN個の整数でふるいを掛けていき、
配列Hにふるいに落ちた各整数の倍数をカウントしていきます。
(下記イメージ参照)

f:id:hgm_blog:20200619173439j:plain
イメージ

最後に配列Hを確認し、与えられた整数のカウントが1のものを数える事で、
答えを求めることが出来ます。(1以外の場合は他の整数で割り切れてしまっているため)

最後に

んー基本的にはABC完をキープすれば茶色になれるってtwitterで優しい人が教えてくれたけど、
中々道のりは長いですね。なるべくABCでWAしないように慎重に回答してコツコツ上げていきます。