接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 241（ABC241）

AtCoder Beginner Contest 241（ABC241）

AtCoderBeginnerContest AtCoderBeginnerContest241 ABC ABC241

atcoder.jp

A - Digit Machine

$ a[a[a[0]]] $ が答え

提出コード

void solve(){
    vector<int> a(10);
    REP(i,10) cin >> a[i];
    cout << a[a[a[0]]] << endl;
}

B - Pasta

mapなどで長さごとに残りの個数を管理しておき、条件を満たすことができるかを判定する

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(M);
    map<int, int> mp;
    REP(i,N){
        cin >> A[i];
        mp[A[i]]++;
    }
    REP(i,M) cin >> B[i];
    bool ok = true;
    REP(i,M){
        if(mp[B[i]] > 0){
            mp[B[i]]--;
        }
        else ok = false;
    }
    cout << (ok ? "Yes" : "No") << endl;
}

C - Connect 6

各マスから下、右、左下、右下の四方向に対しそれぞれ連続した6マスの中に黒マスが4つ以上あれば条件を満たすことができる

提出コード

void solve(){
    int N;
    cin >> N;
    vector<string> S(N);
    REP(i,N) cin >> S[i];
    bool ok = false;
    REP(i,N) REP(j,N){
        int dx[4] = {1, 0, 1, -1};
        int dy[4] = {0, 1, 1, 1};
        REP(d,4){
            int black = 0, white = 0;
            REP(k,6){
                int nh = i + dx[d] * k;
                int nw = j + dy[d] * k;
                if(nh < 0 or nh >= N or nw < 0 or nw >= N) break;
                if(S[nh][nw] == '#') black++;
                else white++;
            }
            if((black == 6) or (black == 5 and white == 1) or (black == 4 and white == 2)){
                ok = true;
            }
        }
    }
    cout << (ok ? "Yes" : "No") << endl;
}

D - Sequence Query

multisetで値を管理しながら愚直に求めればいい

提出コード

void solve(){
    int Q;
    cin >> Q;
    multiset<ll> mst;
    mst.insert(-1);
    mst.insert(2*LINF);
    while(Q--){
        int q;
        cin >> q;
        if(q == 1){
            ll x;
            cin >> x;
            mst.insert(x);
        }
        else if(q == 2){
            ll x, k;
            cin >> x >> k;
            auto itr = mst.upper_bound(x);
            --k;
            if(*itr == 2*LINF or *itr > x) itr--;
            bool ok = true;
            while(k--){
                if(*itr == -1){
                    ok = false;
                    break;
                }
                itr--;
            }
            cout << (ok ? *itr : -1) << endl;
        }
        else if(q == 3){
            ll x, k;
            cin >> x >> k;
            --k;
            auto itr = mst.lower_bound(x);
            bool ok = true;
            if(*itr == 2*LINF){
                ok = false;
                k = 0;
            }
            while(k--){
                itr++;
                if(*itr == 2*LINF){
                    ok = false;
                    break;
                }
            }
            cout << (ok ? *itr : -1) << endl;
        }
    }
}

E - Putting Candies

周期性があるのでダブリングなどで求めることができる

提出コード

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

F - Skate

辿り着けるマスは障害物のあるマスの上下左右の4つのみなのでBFSなどで求めることができる
辿り着けるマスの候補をx, y座標それぞれについて座圧し、その個数分setなどで障害物のあるマスを管理する
今いるマスから次のマスへは二分探索で求めることができる

提出コード

void solve(){
    int H, W, N;
    cin >> H >> W >> N;
    int sh, sw, gh, gw;
    cin >> sh >> sw >> gh >> gw;
    Compress<int> cmp;
    cmp.add(0);
    cmp.add(INF);
    vector<int> X(N), Y(N);
    REP(i,N){
        cin >> X[i] >> Y[i];
        cmp.add(X[i]);
        cmp.add(X[i]-1);
        cmp.add(X[i]+1);
        cmp.add(Y[i]);
        cmp.add(Y[i]-1);
        cmp.add(Y[i]+1);
    }
    cmp.build();
    int sz = cmp.size();
    vector<set<int>> st_x(sz+10), st_y(sz+10);
    st_x[cmp.get(sh)].insert(0);
    st_x[cmp.get(gh)].insert(W+1);
    st_y[cmp.get(sw)].insert(0);
    st_y[cmp.get(gw)].insert(H+1);
    REP(i,sz){
        st_x[i].insert(0);
        st_x[i].insert(W+1);
        st_y[i].insert(0);
        st_y[i].insert(H+1);
    }
    REP(i,N){
        st_x[cmp.get(X[i])].insert(Y[i]);
        st_y[cmp.get(Y[i])].insert(X[i]);
    }

    queue<pair<int, int>> q;
    map<pair<int, int>, int> mp;
    q.emplace(sh, sw);
    mp[{sh, sw}] = 0;
    while(!q.empty()){
        auto [h, w] = q.front(); q.pop();
        {
            // 上
            auto itr = st_y[cmp.get(w)].lower_bound(h);
            --itr;
            int nh = *itr;
            if(nh == 0){}
            else{
                nh++;
                if(!mp.count({nh, w})){
                    q.emplace(nh, w);
                    mp[{nh, w}] = mp[{h, w}] + 1;
                }
            }
        }
        {
            // 下
            auto itr = st_y[cmp.get(w)].lower_bound(h);
            if(*itr != h) itr--;
            itr++;
            int nh = *itr;
            if(nh == H + 1){}
            else{
                nh--;
                if(!mp.count({nh, w})){
                    q.emplace(nh, w);
                    mp[{nh, w}] = mp[{h, w}] + 1;
                }
            }
        }
        {
            // 左
            auto itr = st_x[cmp.get(h)].lower_bound(w);
            itr--;
            int nw = *itr;
            if(nw == 0){}
            else{
                nw++;
                if(!mp.count({h, nw})){
                    q.emplace(h, nw);
                    mp[{h, nw}] = mp[{h, w}] + 1;
                }
            }
        }
        {
            // 右
            auto itr = st_x[cmp.get(h)].lower_bound(w);
            if(*itr != w) itr--;
            itr++;
            int nw = *itr;
            if(nw == W + 1){}
            else{
                nw--;
                if(!mp.count({h, nw})){
                    q.emplace(h, nw);
                    mp[{h, nw}] = mp[{h, w}] + 1;
                }
            }
        }
    }
    cout << (mp[{gh, gw}] ? mp[{gh, gw}] : -1) << endl;
}