接着剤の精進日記

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

トップ > AtCoderBeginnerContest167 > AtCoder Beginner Contest 167（ABC167）

AtCoder Beginner Contest 167（ABC167）

AtCoderBeginnerContest167 AtCoderBeginnerContest ABC167 ABC

atcoder.jp

数を数えられない

A - Registration

substrで比較すればいい
Tをpop_back()するの頭いいね
提出コード

void solve(){
    string S, T;
    cin >> S >> T;
    int n = S.size();
    if(S == T.substr(0,n)){
        cout << "Yes" << endl;
    }
    else cout << "No" << endl;
}

B - Easy Linear Programming

1, 0, -1の順に取れるだけ取っていけばいい

提出コード

void solve(){
    ll A, B, C, K;
    cin >> A >> B >> C >> K;
    ll sum = 0;
    if(A >= K){
        sum += K;
        K = 0;
    }
    else{
        sum += A;
        K -= A;
    }
    if(B >= K){
        K = 0;
    }
    else K -= B;
    sum -= K;
    cout << sum << endl;
}

C - Skill Up

流石にもう解ける人のほうが多いね
bit全探索をする
提出コード

void solve(){
    int N, M, X;
    cin >> N >> M >> X;
    vector<ll> C(N);
    vector<vector<ll>> A(N, vector<ll>(M));
    REP(i,N){
        cin >> C[i];
        REP(j,M){
            cin >> A[i][j];
        }
    }
    ll sum = LINF;
    REP(i,1<<N){
        ll tmp = 0;
        vector<ll> t(N);
        REP(j,N){
            if(i >> j & 1){
                tmp += C[j];
                REP(k,M) t[k] += A[j][k];
            }
        }
        bool ok = true;
        REP(k,M) if(t[k] < X) ok = false;
        if(ok) chmin(sum, tmp);
    }
    if(sum == LINF) sum = -1;
    cout << sum << endl;
}

D - Teleporter

脳死ダブリングをした
周期で見る解法もあるけどダブリング出来るならダブリングのほうがバグらせない気がする
コンテスト中全人類ダブリングできるのかーとなっていた
提出コード

void solve(){
    ll N, K;
    cin >> N >> K;
    vector<int> A(N);
    REP(i,N){
        cin >> A[i];
        --A[i];
    }
    vector<vector<ll>> to(62, vector<ll>(N));
    REP(i,N) to[0][i] = A[i];
    REP(i,60) REP(j,N) to[i+1][j] = to[i][to[i][j]];
    int cur = 0;
    REP(j,60){
        if((K >> j) & 1){
            cur = to[j][cur];
        }
    }
    cout << cur + 1 << endl;
}

E - Colorful Blocks

全人類数え上げがうますぎる
まず隣り合う組を固定することを考える
K = 0のときはM \times (M - 1)^{N-1}通り
K = iのときは、 M \times (M - 1)^{N-1-i}通りあり、隣り合う組の選び方が _{N - 1} C _ i通りとなるのでその積の総和を求めればいい
提出コード

using mint = Fp<MOD>;
BiCoef<mint> bc(202020);

void solve(){
    int N, M, K;
    cin >> N >> M >> K;
    
    mint ans = 0;
    for(int i=0;i<=K;i++){
        ans += mint(M) * modpow(mint(M-1), N-1-i) * bc.com(N-1, i);
    }
    cout << ans << endl;
}

F - Bracket Sequencing

括弧列のときはまず'('を+1、')'を-1としたときに、その総和が0になっている必要がある
また、括弧列を並べたときに、途中で負の値になっている場合は括弧列にはならない
解説放送の考え方がわかりやすかったのでその方針で考える
各文字列に対して、折れ線グラフで考えたときに一番底の部分（最小の値）と最終的な総和のペアを考える
総和が正の時、最小が大きい順かつ、総和が大きい順に取っていけばいい
総和が負になったときが問題になるが、総和が正のものを、折れ線グラフを左から見ている状態とする
そうすると、総和が負のときは折れ線グラフを逆から見たものとすると、総和が正のときと同じ状態とみなせる
そのため、それぞれに対し、今の総和に最小の値を足したときに負になれば"No"となり、そのようにならないときは必ず"Yes"になる
提出コード

void solve(){
    int N;
    cin >> N;
    vector<string> S(N);
    REP(i,N) cin >> S[i];
    vector<pair<int, int>> posi, nega;

    int sum = 0;
    REP(i,N){
        int cnt = 0;
        int mi = 0;
        REP(j,S[i].size()){
            if(S[i][j] == '(') cnt++;
            else cnt--;
            chmin(mi, cnt);
        }
        if(cnt > 0) posi.emplace_back(mi, cnt);
        else nega.emplace_back(mi - cnt, -cnt);
        sum += cnt;
    }
    if(sum != 0){
        cout << "No" << endl;
        return;
    }
    sort(posi.rbegin(), posi.rend());
    sort(nega.rbegin(), nega.rend());
    int cur = 0;
    for(auto [mi, cnt] : posi){
        // cout << mi << " " << cnt << endl;
        if(cur + mi < 0){
            cout << "No" << endl;
            return;
        }
        cur += cnt;
    }
    cur = 0;
    for(auto [mi, cnt] : nega){
        // cout << mi << " " << cnt << endl;
        if(cur + mi < 0){
            cout << "No" << endl;
            return;
        }
        cur += cnt;
    }
    cout << "Yes" << endl;
}

おわりに

数を数えられる人間になりたいね