接着剤の精進日記

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

トップ > AtCoderBeginnerContest > エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）

エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）

AtCoderBeginnerContest AtCoderBeginnerContest202 ABC ABC202

atcoder.jp

A - Three Dice

ある面の裏側は $ 7 $ からその面の数字を引いたものになるので $ 21 - a - b - c $
提出コード

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

B - 180°

問題文のとおりに文字列をreverseしたあとに数字を対応したものに置き換える
提出コード

void solve(){
    string S;
    cin >> S;
    for(char &c : S){
        if(c == '6') c = '9';
        else if(c == '9') c = '6';
    }
    reverse(S.begin(), S.end());
    cout << S << endl;
}

C - Made Up

$ B_{C_j} = x $ を満たす $ x $ の個数を求めたいので、予め $ A $ に出現する $ x $ の個数をカウントしておく
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N), B(N), C(N);
    map<int, int> mp;
    REP(i,N){
        cin >> A[i];
        mp[A[i]]++;
    }
    REP(i,N) cin >> B[i];
    REP(i,N) cin >> C[i];
    ll ans = 0;
    REP(i,N) ans += mp[B[C[i]-1]];
    cout << ans << endl;
}

D - aab aba baa

文字列の先頭から決めていくことを考える
今aが $ A $ 個、bが $ B $ 個残っているとする
aを先頭に置くと辞書順は変わらず、bを置くと、a を $ A - 1 $ 個、b を $ B $ 個使ったときの数だけ辞書順が大きくなる
これは二項係数を使って $ _{A+B-1} C _B $ だけ辞書順が進むと表せる
そのため、 $ K $ より二項係数が大きければ a を使い、そうでなければ bを使って、 $ K = K - _{A+B-1} C _B $ と置き換える
提出コード

void calc_com(vector<vector<ll>> &com){
    com[0][0] = 1;
    REP(i,60) REP(j,60){
        com[i+1][j] += com[i][j];
        com[i+1][j+1] += com[i][j];
    }
}

void solve(){
    int A, B;
    ll K;
    cin >> A >> B >> K;
    K--;
    string ans = "";
    int n = A + B;
    vector<vector<ll>> com(62, vector<ll>(62, 0));
    calc_com(com);
    REP(i,n){
        if(0 < A){
            if(K < com[A+B-1][B]){
                ans += 'a';
                A--;
            }
            else{
                ans += 'b';
                K -= com[A+B-1][B];
                B--;
            }
        }
        else{
            ans += 'b';
            B--;
        }
    }
    cout << ans << endl;
}

E - Xor Distances

オイラーツアー順に行きがけ順と帰りがけ順にindexを割り当てていく
その際、行きがけのときに、根から見た深さごとにそのindexを保存していく
クエリ $ U_i, D_i $ では、深さが $ D_i $ に保存されているindexのうち、 $ U_i $ の部分木の範囲で出現する頂点の個数を答えればいい
$ U_i $ の行きがけ順のindexを $ in_{U_i} $、帰りがけ順のindexを $ out_{U_i} $ とすると、深さ $ D_i $ の配列に出現する $ in _{U_i} \lt x \lt out _{U_i } $ を満たす $ x $ の個数を求めればいい
これは二分探索を使うことで十分高速に求めることが出来る
提出コード

void solve(){
    int N;
    cin >> N;
    vector<vector<int>> G(N);
    REP(i,N-1){
        int p;
        cin >> p;
        --p;
        G[p].emplace_back(i+1);
        G[i+1].emplace_back(p);
    }
    vector<int> in(N), out(N);
    vector<vector<int>> depth(N);
    int cnt = 0;
    auto dfs = [&](auto &&self, int cur, int par=-1, int d=0) -> void{
        in[cur] = cnt++;
        depth[d].emplace_back(in[cur]);
        for(auto nv : G[cur]){
            if(nv == par) continue;
            self(self, nv, cur, d+1);
        }
        out[cur] = cnt++;
    };
    dfs(dfs, 0);
    int Q;
    cin >> Q;
    while(Q--){
        int u, d;
        cin >> u >> d;
        --u;
        cout << lower_bound(depth[d].begin(), depth[d].end(), out[u]) - lower_bound(depth[d].begin(), depth[d].end(), in[u]) << endl;
    }
}