接着剤の精進日記

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

トップ > AtCoderBeginnerContest178 > AtCoder Beginner Contest 178（ABC178）

AtCoder Beginner Contest 178（ABC178）

AtCoderBeginnerContest178 AtCoderBeginnerContest ABC178 ABC

atcoder.jp

久しぶりのHighest

A - Not

0と1の反転は今の値をxとすると 1 - xで出来る
提出コード

void solve(){
    int x;
    cin >> x;
    cout << 1 - x << endl;
}

B - Product Max

こどふぉっぽい
こういうのはだいたい区間の最大と最小に注目すればいい
そのため a \times c, a \times d, b \times c, b \times dの4通りの最大を出力すればいい
提出コード

void solve(){
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << max({a*c, a*d, b*c, b*d}) << endl;
}

C - Ubiquity

難しい
まず全ての場合の数は10^N
次に、0と9を少なくとも1つずつ選んだ場合の数を求めたい
これは包除原理を用いると 0または9を一つも選ばない場合の数はそれぞれ9^N
0と9のどちらも選ばない場合の数は8^Nより 0または9の少なくとも片方が存在しない場合の数は9^N + 9^N - 8^Nとなる
これを全体から引くと10^N - (9^N + 9^N - 8^N)が答えとなる
提出コード

void solve(){
    int N;
    cin >> N;
    mint ans = modpow(mint(10), N) - mint(2) * modpow(mint(9), N) + modpow(mint(8), N);
    cout << ans << endl;
}

D - Redistribution

算数できるらしい、難しい
dp[i] := 和がiになる場合の数としてDPをすると\mathcal{O}(S^2)で解くことが出来る
提出コード

void solve(){
    int S;
    cin >> S;
    vector<ll> dp(2020);
    dp[0] = 1;
    REP(i,S+1){
        vector<ll> next = dp;
        for(int j=3;j<2020;j++){
            if(i + j <= S and dp[i] > 0){
                next[i+j] += dp[i];
                next[i+j] %= MOD;
            }
        }
        dp = next;
    }
    cout << dp[S] << endl;
}

E - Dist Max

いかにも典型っぽい見た目をしているので、ぐぐるとそれっぽいのが出てくるのでコードに移す
典型っぽいので復習でちゃんと理解しておきたいね

ir5.hatenadiary.org
naoyat.hatenablog.jp 提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> x(N), y(N);
    REP(i,N) cin >> x[i] >> y[i];
    vector<ll> tmp(N);
    ll ans = 0;
    for(int i : {-1, 1}){
        for(int j : {-1, 1}){
            REP(k,N){
                tmp[k] = x[k] * i + y[k] * j;
            }
            auto r = minmax_element(tmp.begin(), tmp.end());
            chmax(ans, *r.second - *r.first);
        }
    }
    cout << ans << endl;
}

F - Contrast

復習ACした
はじめに、各整数がAとBに最大幾つ出現するか数える
このmaxがNを超える時、どのように並べても必ず1箇所はA_i = B_iとなってしまうので"No"となる
それ以外の場合、必ず構築できる
まず、与えられた数列Bを降順ソート（reverse）することを考える
そうするとAとBでA_i = B_iとなる正の整数は高々1種類となる（これ天才すぎる）
そのため、被っている箇所を上手いことswapしてあげればいい
実装はqueueとかを使ってswap出来る箇所を持つのが楽そう
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    vector<int> cnt_A(N+10), cnt_B(N+10);
    REP(i,N){
        cin >> A[i];
        cnt_A[A[i]]++;
    }
    REP(i,N){
        cin >> B[i];
        cnt_B[B[i]]++;
    }
    int ma = 0;
    REP(i,N+1) chmax(ma, cnt_A[i] + cnt_B[i]);
    if(ma > N){
        cout << "No" << endl;
        return;
    }

    sort(B.rbegin(), B.rend());
    int num = 0;
    REP(i,N) if(A[i] == B[i]) num = A[i];
    queue<int> q;
    REP(i,N) if(A[i] != num and B[i] != num) q.push(i);
    REP(i,N) if(A[i] == B[i]){
        int idx = q.front(); q.pop();
        swap(B[i], B[idx]);
    }
    cout << "Yes" << endl;
    REP(i,N) cout << B[i] << " ";
    cout << endl;
}