接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 236（ABC236）

AtCoder Beginner Contest 236（ABC236）

AtCoderBeginnerContest AtCoderBeginnerContest236 ABC ABC236

atcoder.jp

A - chukodai

$ a, $ 文字目と $ b $ 文字目をswap

提出コード

void solve(){
    string S;
    cin >> S;
    int a, b;
    cin >> a >> b;
    --a, --b;
    swap(S[a], S[b]);
    cout << S << endl;
}

B - Who is missing?

それぞれの数をカウントして $ A_i = 3 $ なる $ i $ を出力

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,4*N-1){
        int a;
        cin >> a;
        A[--a]++;
    }
    REP(i,N) if(A[i] == 3) cout << i + 1 << endl;
}

C - Route Map

$ S_i $ が $ T_j $ に出現するかどうかをmapなどで管理する

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<string> S(N), T(M);
    map<string, bool> mp;
    REP(i,N){
        cin >> S[i];
        mp[S[i]] = false;
    }
    REP(i,M){
        cin >> T[i];
        mp[T[i]] = true;
    }
    REP(i,N) cout << (mp[S[i]] ? "Yes" : "No") << endl;
}

D - Dance

探索順を工夫することで全探索できる
$ i $ 番目のペアを作成する時に、まだペアに使っていないもののうち、一番左のものを使用することにする
そうすると状態数は最大で $ 15 \times 13 \times \dots \times 1 = 2027025 $ となり全探索で十分に間に合う

提出コード

void solve(){
    int N;
    cin >> N;
    vector<vector<int>> A(2*N, vector<int>(2*N));
    REP(i,2*N) REP(j,i+1,2*N) cin >> A[i][j];
    ll ans = 0;
    auto dfs = [&](auto && self, vector<pair<int, int>> v, vector<bool> used) -> void{
        if(v.size() == N){
            ll sum = 0;
            for(auto [a, b] : v) sum ^= A[a][b];
            chmax(ans, sum);
            return;
        }
        int l = 0;
        REP(i,2*N) if(!used[i]){
            l = i;
            break;
        }
        used[l] = true;
        REP(i,2*N) if(!used[i]){
            v.emplace_back(l, i);
            used[i] = true;
            self(self, v, used);
            used[i] = false;
            v.pop_back();
        }
        used[l] = false;
        return;
    };
    vector<pair<int, int>> v;
    vector<bool> used(2*N);
    dfs(dfs, v, used);
    cout << ans << endl;
}

E - Average and Median

平均値の最大と、中央値の最大に対しそれぞれ二分探索を行う
平均値の最大の場合、平均値を $ m $ とすると、予め $ A_i = A_i - m $ とした状態で選んだものの総和が $ 0 $ 以上であれば条件を満たす
よって、上記をDPで求めながら平均値の最大を二分探索で求める
中央値も同様に、

$$ A_i = \left\{ \begin{array}{c} 1 (A_i \geq m) \\ -1 (A_i \lt m) \end{array} \right. $$ とした状態で選んだものの総和が0より大きいとき条件を満たすので同様に求める

提出コード

void solve(){
    ll N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    {
        auto f = [&](long double m) -> bool{
            vector<long double> dp(N, -LINF);
            dp[0] = A[0] - m;
            dp[1] = A[1] - m;
            REP(i,N){
                if(i + 1 < N) chmax(dp[i+1], dp[i] + A[i+1] - m);
                if(i + 2 < N) chmax(dp[i+2], dp[i] + A[i+2] - m);
            }
            return max(dp[N-2], dp[N-1]) >= 0.0 ? true : false;
        };
        long double l = 0, r = LINF;
        REP(i,200){
            long double m = (l + r) / 2;
            if(f(m)) l = m;
            else r = m;
        }
        printf("%.12Lf\n", l);
    }
    {
        auto f = [&](ll m) -> bool{
            vector<ll> dp(N+1, -INF);
            dp[0] = (A[0] >= m ? 1 : -1);
            dp[1] = (A[1] >= m ? 1 : -1);
            REP(i,N){
                if(i + 1 < N) chmax(dp[i+1], dp[i] + (A[i+1] >= m ? 1 : -1));
                if(i + 2 < N) chmax(dp[i+2], dp[i] + (A[i+2] >= m ? 1 : -1));
            }
            return max(dp[N-1], dp[N-2]) > 0 ? true : false;
        };
        ll l = 0, r = LINF;
        while(r - l > 1){
            ll m = (l + r) >> 1;
            if(f(m)) l = m;
            else r = m;
        }
        printf("%d\n", l);
    }
}

F - Spices

$ c_i $ の昇順にソートした状態で、xorの基底を求める
$ i $ が基底に追加される場合、答えに$ c_i $ を加算する

提出コード

void solve(){
    int N;
    cin >> N;
    vector<LP> v;
    REP(i,(1<<N) - 1){
        int c;
        cin >> c;
        v.emplace_back(c, i+1);
    }
    sort(ALL(v));
    ll ans = 0;
    vector<ll> bases;
    for(auto [c, val] : v){
        for(auto base : bases) chmin(val, val ^ base);
        if(val > 0){
            ans += c;
            bases.emplace_back(val);
        }
    }
    cout << ans << endl;
}