接着剤の精進日記

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

トップ > AtCoderBeginnerContest169 > AtCoder Beginner Contest 169（ABC169）

AtCoder Beginner Contest 169（ABC169）

AtCoderBeginnerContest169 AtCoderBeginnerContest ABC169 ABC

atcoder.jp

最近だめだこれ〜

A - Multiplication 1

A \times Bを出力
提出コード

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

B - Multiplication 2

結構難しい
0が含まれてたら答えが0になるのに注意
それ以外は順に掛け算をしていく
オーバーフローはcur \gt \frac{10^{18}}{a_i}で判定できる
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> a(N);
    bool zero = false;
    REP(i,N){
        cin >> a[i];
        if(a[i] == 0) zero = true;
    }
    if(zero){
        cout << 0 << endl;
        return;
    }
    ll ans = 1;
    REP(i,N){
        if(ans > LINF / a[i]){
            cout << -1 << endl;
            return;
        }
        ans *= a[i];
    }
    cout << ans << endl;
}

C - Multiplication 3

doubleやlong doubleだと誤差で落ちる（本番はlong doubleでも通ったらしい）
小数点以下2桁までしかないので、stringなどで受け取って100倍にしてかけたあと100で割って切り捨てればいい
提出コード

void solve(){
    ll A;
    cin >> A;
    string b;
    cin >> b;
    ll B = 0;
    ll cur = 100;
    REP(i,b.size()){
        if(b[i] == '.') continue;
        B += cur * (b[i] - '0');
        cur /= 10;
    }
    ll ans = A * B / 100;
    cout << ans << endl;
}

D - Div Game

素因数分解をする
各素因数を1個、2個、…と取っていくのが最適
提出コード

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));//p^num
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

void solve(){
    ll N;
    cin >> N;
    auto res = prime_factorize(N);
    ll ans = 0;
    for(auto x : res){
        int cur = 1;
        while(x.second > 0 && x.second >= cur){
            x.second -= cur;
            ans++;
            cur++;
        }
    }
    cout << ans << endl;
}

E - Count Median

中央値になる最大と最小の区間を求める
AとBをそれぞれソートをすると\frac{N}{2}番目の最小はA_{\frac{N}{2}}となる
同様に最大はB_{frac{N}{2}}となるのでB_{\frac{N}{2}} - A_{\frac{N}{2}} + 1が答え
偶数の時も殆ど同様で、(B_{\frac{N}{2}} + B_{\frac{N}{2} - 1}) - (A_{\frac{N}{2}} + A_{\frac{N}{2} - 1}) + 1が答えになる
最小と最大の間は全部作れるいつものあれ
本番はimosっぽくやってWA取れなかったけど素直にソートで良かったね…
提出コード

void solve(){
    ll N;
    cin >> N;
    vector<ll> A(N), B(N);
    REP(i,N) cin >> A[i] >> B[i];
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    if(N & 1){
        ll a = A[N/2];
        ll b = B[N/2];
        cout << b - a + 1 << endl;
    }
    else{
        ll a = A[N/2-1] + A[N/2];
        ll b = B[N/2-1] + B[N/2];
        cout << b - a + 1 << endl;
    }
}

F - Knapsack for All Subsets

解説AC
部分集合Tについての部分集合をUとする
U = \{ x_1, x_2, ..., x_k \} とし、 A_{x_1} + A_{x_2} + ... + A_{x_k} = Sを満たす
A_iを選ぶ時には
1. UにもTにも入れる
2. Tにのみ入れる
3. UにもTにも入れない
の3通りがある
dp[i][j] := i番目を見ているときにUの和がjのときの場合の数と定義する
そうすると、Uに入れるときのみ、dp[i][j] += dp[i][j-A[i]]のように遷移し
Uに入れないときは2. と 3. の2通りあるため、dp[i+1][j] += 2 * dp[i][j]と遷移できる

提出コード

using mint = Fp<MOD2>;

void solve(){
    int N, S;
    cin >> N >> S;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    vector<vector<mint>> dp(N+10, vector<mint>(S+10));
    dp[0][0] = 1;
    REP(i,N){
        REP(j,S+1){
            dp[i+1][j] += dp[i][j] * 2;
            if(j - A[i] >= 0) dp[i+1][j] += dp[i][j-A[i]];
        }
    }
    cout << dp[N][S] << endl;
}