接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

AtCoder Beginner Contest 177（ABC177）

AtCoderBeginnerContest177 AtCoderBeginnerContest ABC177 ABC

A - Don't be late

$T \times S \geq D$ なら"Yes"
提出コード

void solve(){
    ll D, T, S;
    cin >> D >> T >> S;
    if(T * S >= D) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - Substring

長さ|T|のSの全ての部分列とTを比較してその差異の最小値を求める
提出コード

void solve(){
    string S, T;
    cin >> S >> T;
    int n = S.size();
    int m = T.size();
    int ans = INF;
    REP(i,n-m+1){
        int cnt = 0;
        REP(j,m){
            if(S[i+j] != T[j]) cnt++;
        }
        chmin(ans, cnt);
    }
    cout << ans << endl;
}

C - Sum of product of pairs

ちょっと難し目？
各 $i$ についての和は $A_i \times A_{i+1} + A_i \times A_{i+2} + ... + A_i \times A_N$ となり
$A_i \times (A_{i+1} + A_{i+2} + ... + A_N)$ となるので
累積和を用いればこの答えを求めることが出来る
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> A(N);
    vector<mint> cum(N+1);
    REP(i,N){
        cin >> A[i];
        cum[i+1] = cum[i] + A[i];
    }
    mint ans = 0;
    REP(i,N){
        ans += (cum[N] - cum[i+1]) * A[i];
    }
    cout << ans << endl;
}

D - Friends

グループの全員が友達であるようなグループに分け、その人数を求める
これはUnionFindやDFSなどで求めることが出来る
すべての人について、グループ内に友達がいないように分けるには
上述のグループの人たちが全て異なるグループに別れれば良い
そのため、このグループの人数の最大を出力すればいい
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    UnionFind uf(N);
    REP(i,M){
        int a, b;
        cin >> a >> b;
        --a, --b;
        uf.unite(a, b);
    }
    int ans = 0;
    vector<int> cnt(N);
    REP(i,N){
        cnt[uf.root(i)]++;
        chmax(ans, cnt[uf.root(i)]);
    }
    cout << ans << endl;
}

E - Coprime

よくわからなかったのでosa_k法を使った
各 $A_i$ の素因数の個数をmapなどで管理をする
"pairwise coprime"を満たすには、 $A_i$ の素因数がそれ以降の $A_j$ で出現しなければいい
"pairwaise coprime"でなく、 $GCD(A_i,...,A_N) = 1$ の時、"setwise coprime"、それ以外は"not coprime"を出力すればいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    int g = 0;
    REP(i,N){
        cin >> A[i];
        g = gcd(g, A[i]);
    }
    auto spf = smartPrimeFactors(1010101);
    map<int, int> mp;
    for(int i=1;i<N;i++){
        auto res = factorize(A[i], spf);
        for(auto [k, v] : res) mp[k] += v;
    }
    bool ok = true;
    REP(i,N-1){
        auto res = factorize(A[i], spf);
        for(auto [k, v] : res){
            mp[k] -= v;
            if(mp[k] > 0){
                ok = false;
                break;
            }
        }
    }
    if(ok) cout << "pairwise coprime" << endl;
    else if(g == 1) cout << "setwise coprime" << endl;
    else cout << "not coprime" << endl;
}