接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 235（ABC235）

AtCoder Beginner Contest 235（ABC235）

AtCoderBeginnerContest AtCoderBeginnerContest235 ABC ABC235

atcoder.jp

A - Rotate

$ abc + bca + cab = 100(a + b + c) + 10(a + b + c) + (a + b + c) = 111(a + b + c) $ となるのでこれを出力

提出コード

void solve(){
    string s;
    cin >> s;
    int a = s[0] - '0';
    int b = s[1] - '0';
    int c = s[2] - '0';
    cout << 100 * (a + b + c) + 10 * (a + b + c) + a + b + c << endl;
}

B - Climbing Takahashi

$ H_0 \lt H_1 \lt \dots \lt H_i $ を満たす $ i $ を求める

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> H(N);
    REP(i,N) cin >> H[i];
    int ma = -INF;
    REP(i,N){
        if(!chmax(ma, H[i])) break;
    }
    cout << ma << endl;
}

C - The Kth Time Query

要素 $ a_i $ ごとに出現したインデックスを二次元配列などで管理する

提出コード

void solve(){
    int N, Q;
    cin >> N >> Q;
    vector<int> a(N);
    vector<int> x(Q), k(Q);
    Compress<int> cmp;
    REP(i,N){
        cin >> a[i];
        cmp.add(a[i]);
    }
    REP(i,Q){
        cin >> x[i] >> k[i];
        --k[i];
        cmp.add(x[i]);
    }
    cmp.build();
    int sz = cmp.size();
    vector<vector<int>> v(sz);
    REP(i,N){
        v[cmp.get(a[i])].emplace_back(i);
    }
    REP(i,Q){
        if(v[cmp.get(x[i])].size() <= k[i]) cout << -1 << endl;
        else cout << v[cmp.get(x[i])][k[i]] + 1 << endl;
    }
}

D - Multiply and Rotate

操作によって得られる整数への距離（操作回数）を考えると最短経路問題として解ける
$ N $ より大きい整数への操作もあり得るので気をつける

提出コード

void solve(){
    int a, N;
    cin >> a >> N;
    vector<ll> dist(N*10+10, LINF);
    priority_queue<LP, vector<LP>, greater<LP>> pq;
    dist[0] = 0;
    pq.emplace(0, 1);
    while(!pq.empty()){
        auto [d, num] = pq.top(); pq.pop();
        if(dist[num] < d) continue;
        if(num * a <= N * 10){
            if(chmin(dist[num*a], d + 1)){
                pq.emplace(dist[num*a], num*a);
            }
        }
        if(num >= 10 and num % 10 != 0){
            int cnt = 0;
            int tmp = num;
            int cur = 1;
            while(tmp > 0){
                cnt++;
                tmp /= 10;
            }
            int nxt = num / 10 + (num % 10 * pow(10, cnt-1));
            if(nxt <= N * 10 and chmin(dist[nxt], d + 1)) pq.emplace(dist[nxt], nxt);
        }
    }
    cout << (dist[N] == LINF ? -1 : dist[N]) << endl;
}

E - MST + 1

最小全域木を作り、$ u_i, v_i $ のパス上の辺の重みの最大を $ ma_i $ とすると、$ ma_i \gt w_i $ ならYes、そうでないならNoとなる
これはHLDとセグ木で求められる
想定解はクエリの辺も含めた辺の集合でクラスカル法を行う

提出コード

void solve(){
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> A(M), B(M), C(M);
    REP(i,M){
        cin >> A[i] >> B[i] >> C[i];
        --A[i], --B[i];
    }
    vector<int> idx(M);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int x, int y){
        return C[x] < C[y];
    });
    UnionFind uf(N);
    HLD hld(N);
    vector<bool> used(M);
    ll sum = 0;
    for(auto i : idx){
        if(uf.issame(A[i], B[i])) continue;
        used[i] = true;
        sum += C[i];
        uf.unite(A[i], B[i]);
        hld.add_edge(A[i], B[i]);
    }
    hld.build();
    SegTree<long long> seg(N, [](long long a, long long b) {
        return max(a, b);
    },
    0);
    for(auto i : idx) if(used[i]){
        auto a = hld.vid[A[i]];
        auto b = hld.vid[B[i]];
        seg.set(max(a, b), C[i]);
    }
    seg.build();
    REP(i,Q){
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        ll ma = 0;
        for(auto [l, r] : hld.for_each_edge(u, v)){
            chmax(ma, seg.get(l, r));
        }

        if(ma > w) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

F - Variety of Digits

$ dp[i][j][k][l] := i $ 番までを見たとき、使った数の集合が $ j $、 $ N $ 以下が確定しているかどうか $ (k) $、leading zeroかどうか $ (l) $ のときの総和としてDPを行う
今見ている状態の総和に、$ d $ を加算するときに今の状態の個数を $ cnt[i][j][k][l] $ として $ d \times cnt[i][j][k][l] $ 加算する必要があるので、個数の配列を別に用意しDP配列と一緒に更新していく

提出コード

ll dp[10101][2048][2][2];
int cnt[10101][2048][2][2];

void solve(){
    string N;
    int M;
    cin >> N >> M;
    vector<int> C(M);
    int goal = 0;
    REP(i,M){
        cin >> C[i];
        goal |= (1 << C[i]);
    }
    int sz = N.size();
    REP(i,10101) REP(j,2048) REP(k,2) REP(l,2){
        dp[i][j][k][l] = 0;
        cnt[i][j][k][l] = 0;
    }
    cnt[0][0][0][0] = 1;
    REP(i, sz) REP(j, 1LL<<11) REP(k, 2) REP(l, 2) if(cnt[i][j][k][l] > 0){
        ll lim = k==0 ? N[i]-'0' : 9;
        REP(d, lim+1) {
            int nj = j, nk = k || d<lim, nl = l || d!=0;
            if(nl==1) nj |= 1LL<<d;
            cnt[i+1][nj][nk][nl] += cnt[i][j][k][l];
            cnt[i+1][nj][nk][nl] %= MOD2;
            dp[i+1][nj][nk][nl] += ((dp[i][j][k][l] % MOD2) * 10) % MOD2 + (d * cnt[i][j][k][l]) % MOD2;
            dp[i+1][nj][nk][nl] %= MOD2;
        }
    }
    mint ans = 0;
    REP(j,1<<11) REP(k,2) REP(l,2) if((j & goal) == goal) ans += dp[sz][j][k][l];
    cout << ans << endl;
}