AtCoder Beginner Contest 167 ABC167 参加記

5完で青パフォでした。ムーブ的にはよかったと思います。

提出へのリンク

f:id:coonevo:20200511003519p:plain — 順位表

A - Registration
B - Easy Linear Programming
C - Skill Up
D - Teleporter
E - Colorful Blocks
F - Bracket Sequencing

A - Registration

pop_back()するのが最適っぽいです。

int main() {

    string s, t;
    cin >> s >> t;
    int N = s.size();
    rep(i, N) {
        if (s[i] != t[i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

B - Easy Linear Programming

大きい順に貪欲にとっていけばよく、-1まで取らないとならないときは引き算しましょう。

int main() {

    ll a,b,c,k;
    cin >> a >> b >> c >> k;
    if(k > a+b){
        cout << a - (k-a-b) << endl;
        return 0;
    }
    cout << min(k, a) << endl;
}

C - Skill Up

Nが小さいのでbit全探索しましょう。これ5分でかけたの割とすごくないですか（自画自賛）

int main() {

    ll N,M,X;
    cin >> N >> M >> X;
    vector<ll> C(N);
    vvec<ll> A(N,vec<ll>(M));
    rep(i,N){
        cin >> C[i];
        rep(j,M){
            cin >> A[i][j];
        }
    }
    ll ans = INFLL;
    for(int s = 0; s < bit(N);s++){
        ll tmp = 0;
        vector<ll> sum(M,0);
        rep(i,N){
            if(s & bit(i)){
                tmp += C[i];
                rep(j,M){
                    sum[j] += A[i][j];
                }
            }
        }
        bool ok = true;
        rep(j,M){
            if(sum[j] < X)ok = false;
        }
        if(ok){
            chmin(ans, tmp);
        }
    }
    if(ans == INFLL){
        cout << -1 << endl;
        return 0;
    }
    cout << ans << endl;
}

D - Teleporter

ループ検出してやるだけですが、最初からではなく途中からループに入る場合が難しいです。deque使って管理するとわかりやすい気もしますが、めんどくさいです。また、ループに入る前でいい場合でWAを出しました。辛かったです。

int main() {

    ll N, K;
    cin >> N >> K;
    vector<int> A(N);
    rep(i,N){
        cin >> A[i];
        A[i]--;
    }
    vector<bool> used(N, false);
    deque<int> mv;
    int cur = 0;
    while(1){
        used[cur] = true;
        mv.push_back(cur+1);
        int nx = A[cur];
        if(used[nx]){
            mv.push_back(nx+1);
            break;
        }
        cur = nx;
    }
    if(K < (ll)mv.size()){
        cout << mv[K] << endl;
        return 0;
    }
    while(true){
        if(mv.front() == mv.back()){
            mv.pop_front();
            K--;
            break;
        }
        else{
            K--;
            mv.pop_front();
        }
    }
    int sz = mv.size();
    cout << mv[K%sz] << endl;
}

E - Colorful Blocks

同じ色の仕切りが $i$ 個のとき、異なる色の仕切りが $_{N-1} C_{N-1-i}$ で、その中を異なるいろで塗る方法は $M * (M-1)^{N-1-i}$ 通りあります。この $i$ を $0 \le i \le K$ まで足せばいいです。

int main() {
    
    ll N,M,K;
    cin >> N >> M >> K;
    mint ans = 0;
    //同じ色の組はi組
    //違う色の組がN-1-i組
    rep(i,K+1){
        int cnt = N - 1 - i;
        mint add = 1;
        //仕切りをcnt個選ぶ
        add *= C.Comb(N-1,cnt);
        add *= M;
        add *= mint(M-1).modpow(cnt);
        ans += add;
    }
    cout << ans << endl;
}