AtCoder Beginner Contest 170 ABC170 参加記

3完で緑パフォでした。Dでvectorやmapを使うのをやめたら通ったので泣きそうです。

-> 追記：vectorは問題なくて、mapのlogがTLEの原因でした。

• 提出へのリンク

C - Fobidden List

0 ~ 1000くらいまで、確認します。に含まれるかどうかを確認するためにmapで管理し、Xとの差を求め小さいものに更新します。chminなどを使うと複数あるときに二個目は更新されないので嬉しいです。

int main() {
    ll X, N;
    cin >> X >> N;
    vector<ll> p(N);
    map<ll,int> mp;
    rep(i, N){
        cin >> p[i];
        mp[p[i]]++;
    }
    ll diff = INFLL;
    ll ans = -1;
    rep(i,1000){
        if(mp[i] == 0 && chmin(diff, abs(X - i))){
            ans = i;
        }
    }
    cout << ans << endl;
}

D - Not Divisible

全てのについて約数を列挙して確認すると、C++でかつ定数倍高速化した場合ギリギリ通ります。

template<typename T>
vector<T> divisor(T N) {
    vector<T> res;
    for(T i = 1; i * i <= N; i++){
        if(N % i == 0){
            res.push_back(i);
            if(i * i != N)res.push_back(N / i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

int A[200010];
int mp[2000100];
int main() {
    int N;
    cin >> N;
    rep(i, N){
        cin >> A[i];
        mp[A[i]]++;
    }
    int ans = 0;
    rep(i,N){
        if(mp[A[i]] > 1)continue;
        bool ok = true;
        mp[A[i]]--;
        auto v = divisor(A[i]);
        for(auto &p: v){
            if(mp[p] > 0){
                ok = false;
                break;
            }
        }
        mp[A[i]]++;
        if(ok)ans++;
    }
    cout << ans << endl;
}

別解として、を昇順ソートした上で前からその倍数を数えていっても間に合います。これは、この問題と同じ発想です。

atcoder.jp

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    vector<ll> cnt(1000100,0);
    vector<bool> ok(1000100, true);
    rep(i, N){
        cin >> A[i];
        cnt[A[i]]++;
    }
    sort(all(A));
    int ans = 0;
    rep(i,N){
        if(cnt[A[i]] == 1 && ok[A[i]])ans++;
        if(!ok[A[i]])continue;
        for(int j = A[i]; j <= 1000000;j += A[i]){
            ok[j] = false;
        }
    }
    cout << ans << endl;
}