AtCoder Beginner Contest 206（ABC206）

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 206（Sponsored by Panasonic）での成績：832位
パフォーマンス：1576相当
レーティング：1435→1450 (+15) :)#AtCoder #ABC206（SponsoredbyPanasonic） https://t.co/VGN9StBFUT

— ボンド@競プロ (@bond_cmprog) June 19, 2021

A - Maxi-Buying

$ \lfloor \frac{108N}{100} \rfloor $ として整数値で判定
提出コード

void solve(){
    int N;
    cin >> N;
    if(108 * N / 100 == 206) cout << "so-so" << endl;
    else if(108 * N / 100 < 206) cout << "Yay!" << endl;
    else cout << ":( " << endl;
}

B - Savings

$ i $ 日目の貯金箱の中身は $ \frac{i (i + 1)}{2} $ であるので $ \sqrt{N} $ 程度までループを回せばいい
提出コード

void solve(){
    ll N;
    cin >> N;
    ll cur = 0;
    REP(i,101010){
        if((ll)i * (i + 1) / 2 >= N){
            cout << i << endl;
            return;
        }
    }
}

C - Swappable

$ A_i $ を見ているとき、$ A_i \neq A_j (i \lt j) $ を満たすものの個数は、$ N - i - cnt_{A_i} $ であるので、mapなどで配列 $ A $ の要素の個数を持ちながら 各 $ A_i $ について条件を満たすものの個数を数える
提出コード

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

D - KAIBUNsyo

$ A_i, A_{N-i-1} $ を同じグループにすると考える
そうすると、同じグループに属する整数はすべて操作によってある整数 $ y $ にする必要がある
あるグループの集合を $ X $ とすると必要な操作回数は $ |X| - 1 $ 回となる
そのため、UnionFindなどで連結成分を管理し、連結成分ごとに必要な操作回数を求めその総和が答え
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    UnionFind uf(202020);
    REP(i,N/2) uf.unite(A[i], A[N-i-1]);
    set<int> st;
    REP(i,202020) st.insert(uf.root(i));
    cout << 202020 - (int)st.size() << endl;
}

E - Divide Both

$ x \lt y $ であるとして答えを求め、最後に2倍する
$ g \neq 1 $ であるとき、$ x, y $ が互いに素でないものの個数を数える
これは各素因数が高々1つ含まれるような整数について、その倍数がいくつ存在するかを包除原理によって求める
また、$ g \neq 1 $ かつ $ \frac{x}{g} = 1 $ を満たすようなものは $ \frac{R}{x} - 1 $ だけ存在するので、上記で求めた個数からこの個数を引いてあげる
提出コード

void solve(){
    int L, R;
    cin >> L >> R;
    ll ans = 0;
    vector<ll> cnt(R+1);
    for(ll i=2;i<=R;i++){
        if(cnt[i] != 0) continue;
        for(ll j=i;j<=R;j+=i) cnt[j]++;
        for(ll j=i*i;j<=R;j+=i*i) cnt[j] = -LINF;
    }
    for(ll i=2;i<=R;i++){
        if(cnt[i] < 0) continue;
        ll num = R / i - (L - 1) / i;
        if(cnt[i] % 2 == 1) ans += num * (num - 1) / 2;
        else ans -= num * (num - 1) / 2;
    }
    for(ll i=max(2, L);i<=R;i++) ans -= (R / i - 1);
    cout << 2LL * ans << endl;
}