接着剤の精進日記

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

トップ > AtCoderBeginnerContest172 > AtCoder Beginner Contest 172（ABC172）

AtCoder Beginner Contest 172（ABC172）

AtCoderBeginnerContest172 AtCoderBeginnerContest ABC172 ABC

atcoder.jp

A - Calc

問題文の通りa + a^2 + a^3を出力
提出コード

void solve(){
    int a;
    cin >> a;
    cout << a + a*a + a*a*a << endl;
}

B - Minor Change

S_i \neq T_iの個数を数える
提出コード

void solve(){
    string S, T;
    cin >> S >> T;
    int cnt = 0;
    REP(i,S.size()) if(S[i] != T[i]) cnt++;
    cout << cnt << endl;
}

C - Tsundoku

いつもより難しめ？
取り敢えず貪欲で考えてみるけど後々得になるパターンがあって駄目そう
片方を幾つ取るかを固定してみると、もう片方は累積和と二分探索を使うことで\mathcal{O}(\log N)で求めることが出来る
実装はC++だとupper_boundを使うのが一番楽そう
提出コード

void solve(){
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> A(N), B(M);
    vector<ll> cum(N+1);
    REP(i,N) cin >> A[i];
    REP(i,M) cin >> B[i];
    for(int i=0;i<N;i++) cum[i+1] = cum[i] + A[i];
    cum.push_back(LINF);
    int ans = 0;
    ll sum = 0;
    REP(i,M+1){
        if(i > 0) sum += B[i-1];
        if(sum > K) break;
        int num = upper_bound(cum.begin(), cum.end(), K - sum) - cum.begin() - 1;
        chmax(ans, num + i);
    }
    cout << ans << endl;
}

D - Sum of Divisors

想定解が綺麗
本番はosa_k法を使って1 \leq i \leq Nに対して素因数分解を行い約数の組み合わせの個数を求めた
これはちょっと無駄があって、素因数分解をしなくてもiごとにその倍数を加算していく方針でも調和級数となって求めることが出来る
さらにこの調和級数部分は等差数列の和として求めることが出来る
これが想定解で\mathcal{O}(N)で解くことが出来る
\mathcal{O}(\sqrt N)でも解けるらしい？
提出コード（osa_k法）

template<typename T>
vector<T> smartPrimeFactors(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, T> factorize(T x, vector<T> &spf) {
    map<T, T> ret;
    while (x > 1) {
        ret[spf[x]]++;
        x /= spf[x];
    }
    //sort(ret.begin(), ret.end());
    return ret;
}
 
void solve(){
    int N;
    cin >> N;
    auto spf = smartPrimeFactors(N);
    ll ans = 0;
    for(int i=1;i<=N;i++){
        auto res = factorize(i, spf);
        ll tmp = 1;
        for(auto [a, b] : res) tmp *= (b + 1);
        ans += (ll)i * tmp;
    }
    cout << ans << endl;
}

提出コード（調和級数）

void solve(){
    int N;
    cin >> N;
    ll ans = 0;
    for(int i=1;i<=N;i++){
        for(int j=i;j<=N;j+=i) ans += j;
    }
    cout << ans << endl;
}

提出コード（想定解）

void solve(){
    int N;
    cin >> N;
    ll ans = 0;
    for(int i=1;i<=N;i++){
        ll n = N / i;
        ans += n * (n + 1) / 2 * (ll)i;
    }
    cout << ans << endl;
}

E - NEQ

まず、A_i = B_iとなるような個数kを固定して考えてみる
この時、その選び方はM個の中からA_i = B_iになるものをk個順番に並べるのに _M P _k通り
それ以外の部分をAとBそれぞれM-k個の中からN-k個を順番に並べるのに (_{M-k} P _{N-k})^2通りとなる
また、N個のうちどのk個を選ぶかで _{N} C _k通り出来る
よってkを固定したときの場合の数は _{N} C _k \times {} _{M} P _k \times (_{M-k} P _{N-k})^2となる
問題は、任意のiについてA_i \neq B_iを満たすものを数える必要があるが、これは包除原理によって求めることが出来る
各kについて、 (-1)^k \times {} _{N} C _ k \times {} _{M} P _k \times (_{M-k} P _{N-k})^2を求めてその総和が答えとなる
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    mint ans = 0;
    for(int k=0;k<=N;k++){
        mint val = bc.com(N, k) * bc.perm(M, k) * bc.perm(M-k, N-k) * bc.perm(M-k, N-k);
        if(k & 1) ans -= val;
        else ans += val;
    }
    cout << ans << endl;
}

F - Unfair Nim

操作後のA_1, A_2の数をx, yと置くとNimの必勝法から
x \oplus y \oplus A_3 \oplus ... \oplus A_N = 0となれば良いことがわかる
上記のA_3 \oplus ... \oplus A_Nをzとすると
x + y = A_1 + A_2, x \oplus y = zを満たせば良い
また移動の条件として 1 \leq x \leq A_1を満たす必要がある
xorの性質を考えると x + y \lt zの時は不可能なので-1となる
ここで x + y = 2 (x & y) + x \oplus yが成り立つことを考えると
x & y = \frac{x + y - z}{2}となる
この時、x & yが非負整数にならないと不可能
また、x & y とzで共通しているbitがあればその場合も不可能
それ以外の場合、条件を満たす範囲で上位bitから貪欲にx & yにbitを割り振っていけばいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<ll> a(n);
    REP(i,n) cin >> a[i];
    ll z = 0;
    for(int i=2;i<n;i++) z ^= a[i];
    if(a[0] + a[1] < z){
        cout << -1 << endl;
        return;
    }
    ll xy = a[0] + a[1] - z;
    if(xy & 1){
        cout << -1 << endl;
        return;
    }
    xy >>= 1;
    if(xy & z){
        cout << -1 << endl;
        return;
    }
    ll ans = xy;
    for(int i=40;i>=0;i--){
        if((z >> i & 1) && ans + (1LL << i) <= a[0]) ans += (1LL << i);
    }
    if(ans == 0 || ans > a[0]) cout << -1 << endl;
    else cout << a[0] - ans << endl;
}