AtCoder Beginner Contest 177 ABC177 参加記

5完2ペナで青パフォでした。初の青パフォstreak2で嬉しいです。

jjjjjjjtgpptmjjさんのAtCoder Beginner Contest 177での成績：605位
パフォーマンス：1732相当
レーティング：1371→1412 (+41) :)
Highestを更新し、3 級になりました！#AtCoder #ABC177 https://t.co/KW2mCcgR3n

— naga@精進 (@longeqe) 2020年8月30日

A - Don't be late

問題へのリンク

解説

時間を計算して比較します。がで割り切れない場合、切り捨てになってしまうので、切り上げを使って比較します。

実装

int main() {
    ll D, T, S;
    cin >> D >> T >> S;
    cout << ((D + S - 1) / S <= T ? "Yes" :"No") << endl;
}

B - Substring

問題へのリンク

解説

で処理します。substr関数を使うとわかりやすいかもしれませんが、指定した長さが取れない場合に後ろをカットする仕様なので、気をつけましょう。これで1ペナはきました。

実装

int main() {

    string S, T;
    cin >> S >> T;
    int N = S.size();
    int M = T.size();
    ll ans = INFLL;
    for(int i = 0; i < N; i++){
        string tmp = S.substr(i, M);
        if(tmp.size() < M)continue;
        ll cnt = 0;
        rep(j,M)cnt += T[j] != tmp[j];
        chmin(ans, cnt);
    }
    cout << ans << endl;
}

C - Sum of product of pairs

問題へのリンク

解説

kyopro_friendsさんの方法で実装しました。組みを全て列挙したいとき、この表を思い浮かべると計算量が良い方法が思い浮かんだりします。

フェネック「C問題は ((ΣAi)^2 - Σ(Ai^2))/2 が答えだねー。この問題みたいに、「i<jの全ての組(i,j)について……」って問題で、「全ての組(i,j)について計算してからi=jの分を引いて2で割る」っていうのよく使うテクニックだから覚えておくといいよー」 pic.twitter.com/1stRIjuqj4

— 競技プログラミングをするフレンズ (@kyopro_friends) 2020年8月29日

ちなみにここでもオーバーフローで1ペナはきました。本当に水色ですか？

実装

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    rep(i,N)cin >> A[i];
    ll sum = accumulate(all(A), 0LL);
    mint ans = 0;
    rep(i,N){
        ans += mint(A[i]) * mint(sum - A[i]);
    }
    cout << ans/2 << endl;
}

D - Friends

問題へのリンク

解説

最も人数の多い友達関係を全員違うグループに分けて、それ以下のグループはそこに詰めていけば達成でき、これが最小です。実装はUnionFindでもグラフにしてDFS, BFSで連結成分でもいいと思います。

実装

int main() {

    int N, M;
    cin >> N >> M;
    UnionFind T(N);
    rep(i,M){
        int a, b;
        cin >> a >> b;
        a--,b--;
        T.unite(a,b);
    }
    int ans = 0;
    rep(i,N)chmax(ans, T.size(i));
    cout << ans << endl;
}

E - Coprime

問題へのリンク

解説

高速素因数分解

高速素因数分解で殴りました。数の上限がある程度小さいとき、複数クエリに高速に答える手法です。 説明はganariyaさんの記事がわかりやすいです。

https://t.co/CrqrsI3csh

— ganariya (@ganariya) 2020年8月29日

調和級数

AtCoder公式解説放送では調和級数を用いた方法が説明されていました。

www.youtube.com

鳩の巣原理

愚直な素因数分解を繰り返しても、ある素因数が二回現れるまでの更新は高々回であるので、それでも解けます。ちなみに愚直に毎回素因数分解を行って確認してもC++なら間に合うそうです。この前もそうでしたね。

実装

template<typename T>
vector<T> smallest_prime_factors(T n) {

    vector<T> spf(n + 1);
    for (int i = 0; i <= n; i++) spf[i] = i;


    for (T i = 2; i * i <= n; i++) {

        // 素数だったら
        if (spf[i] == i) {

            for (T j = i * i; j <= n; j += i) {

                // iを持つ整数かつまだ素数が決まっていないなら
                if (spf[j] == j) {
                    spf[j] = i;
                }
            }
        }
    }

    return spf;
}

template<typename T>
map<T, int> factolization(T x, vector<T> &spf) {
    // vector<T> ret;
    map<T, int> mp;
    while (x != 1) {
        // ret.push_back(spf[x]);
        mp[spf[x]]++;
        x /= spf[x];
    }
    // sort(ret.begin(), ret.end());
    // return ret;
    return mp;
}
int main(){
    constexpr int MAX = 1000000;

    auto spf = smallest_prime_factors(MAX);

    int Q;
    cin >> Q;
    vector<int> v(MAX, 0);
    ll G = -1;
    while (Q--) {
        int x;
        cin >> x;
        if(G == -1)G = x;
        else{
            G = gcd(G, x);
        }
        auto result = factolization(x, spf);
        // for (auto z: result)cout << z << " ";
        // cout << endl;
        // print(result);
        for(auto p: result){
            v[p.first]++;
        }
    }
    bool ok = true;
    rep(i,MAX)if(v[i] >= 2)ok = false;
    if(ok){
        cout << "pairwise coprime" <<endl;
    }
    else if(G == 1){
        cout << "setwise coprime" << endl;
    }
    else{
        cout << "not coprime" << endl;
    }
    return 0;
}

F - I hate Shortest Path Problem

問題へのリンク

まだわかっていません。