接着剤の精進日記

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

マイナビプログラミングコンテスト2021(AtCoder Beginner Contest 201)

atcoder.jp

A - Tiny Arithmetic Sequence

next_permutationで全探索した
よく考えるとソートをして条件を満たしているか確認すればいい
提出コード

void solve(){
    vector<int> A(3);
    REP(i,3) cin >> A[i];
    sort(A.begin(), A.end());
    do{
        if(A[2] - A[1] == A[1] - A[0]){
            cout << "Yes" << endl;
            return;
        }
    }while(next_permutation(A.begin(), A.end()));
    cout << "No" << endl;
}

B - Do you know the second highest mountain?

高さで降順ソートをし、2番目の高さになる元のインデックスの山の名前を答えればいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<string> S(N);
    vector<int> T(N);
    REP(i,N) cin >> S[i] >> T[i];
    vector<int> idx(N);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b){
        return T[a] > T[b];
    });
    cout << S[idx[1]] << endl;
}

C - Secret Number

長さが4桁の文字列なので全探索をする
4つの数字のいずれかがxなら条件を満たさない
また、選んだ数字以外にoになっている数字があればそれも条件を満たさない
それ以外であれば条件を満たしているのでこれを数える
提出コード

void solve(){
    string S;
    cin >> S;
    int cnt = 0;
    REP(i,10) REP(j,10) REP(k,10) REP(l,10){
        if(S[i] == 'x') continue;
        if(S[j] == 'x') continue;
        if(S[k] == 'x') continue;
        if(S[l] == 'x') continue;
        bool ok = true;
        REP(m,10) if(m != i and m != j and m != k and m != l){
            if(S[m] == 'o') ok = false;
        }
        if(ok) cnt++;
    }
    cout << cnt << endl;
}

D - Game in Momotetsu World

高橋くんの得点を $ sum_t $ 、青木くんの得点を $ sum_a $ とする
高橋くんの立場で考えると、$ sum_t - sum_a $ を最大化したく、青木くんはこれを最小化したい
よって、今いるマスの手番が高橋くんなら上記を最大化するように、青木くんなら上記を最小化するようにDPで求めればいい
提出コード

void solve(){
    int H, W;
    cin >> H >> W;
    vector<string> fi(H);
    REP(i,H) cin >> fi[i];
    vector<vector<int>> A(H, vector<int>(W));
    REP(i,H) REP(j,W){
        if(fi[i][j] == '+') A[i][j] = 1;
        else A[i][j] = -1;
    }
    vector dp(H, vector(W, 0));
    vector used(H, vector(W, 0));
    auto memo = [&](auto && self, int h, int w) -> int{
        if(h == H - 1 and w == W - 1) return dp[h][w] = 0;
        if(used[h][w]) return dp[h][w];
        used[h][w] = 1;
        if((h + w) % 2 == 0){
            int res = -INF;
            if(h + 1 < H) chmax(res, self(self, h+1, w) + A[h+1][w]);
            if(w + 1 < W) chmax(res, self(self, h, w+1) + A[h][w+1]);
            return dp[h][w] = res;
        }
        else{
            int res = INF;
            if(h + 1 < H) chmin(res, self(self, h+1, w) - A[h+1][w]);
            if(w + 1 < W) chmin(res, self(self, h, w+1) - A[h][w+1]);
            return dp[h][w] = res;
        }
    };
    memo(memo, 0, 0);
    if(dp[0][0] == 0) cout << "Draw" << endl;
    else if(dp[0][0] > 0) cout << "Takahashi" << endl;
    else cout << "Aoki" << endl;
}

E - Xor Distances

ある頂点を適当に根とした木を考える
根 $ x $ から他の頂点 $ i $ への距離を $ dist_{x, i} $ とする
ある二頂点 $ (i, j) $ のパスの距離は最小共通祖先を考えると $ dist_{i, j} = dist_{x,i} \oplus dist_{x,j} $ と表せる
よって $ 1 \leq i \lt j \leq N $ を満たすパスの総和を求めればいい
これはbitの各桁ごとに見るといい
$ dist_{x, i} $ の $ k $ 番目のbitが立っているものの個数を $ cnt_1 $、立っていないものの個数を $ cnt_0 $ とすると、$ 2^{k - 1} \times cnt_0 \times cnt_1 $ が総和に寄与する
これを各桁ごとに求めた総和が答え
提出コード

void solve(){
    int N;
    cin >> N;
    vector<vector<pair<int, ll>>> g(N);
    REP(i,N-1){
        ll u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    vector dist(N, 0LL);
    auto dfs = [&](auto && self, int cur, int par=-1, ll sum=0) -> void{
        dist[cur] = sum;
        for(auto [nv, w] : g[cur]){
            if(nv == par) continue;
            self(self, nv, cur, sum^w);
        }
    };
    dfs(dfs, 0, -1);
    mint ans = 0;
    REP(i,60){
        vector<mint> cnt(2, 0);
        REP(j,N) cnt[dist[j]>>i&1] += 1;
        ans += cnt[0] * cnt[1] * (1LL << i);
    }
    cout << ans << endl;
}