AtCoder Beginner Contest 176（ABC176） - 接着剤の精進日記

atcoder.jp

レート増えたから良し！ｗ
Bondo416さんのAtCoder Beginner Contest 176での成績：1120位
パフォーマンス：1456相当
レーティング：1359→1369 (+10) :)#AtCoder #ABC176 https://t.co/RfXqjjyrqy
— ボンド@競プロ (@bond_cmprog) August 22, 2020

A - Takoyaki

$\lceil \frac{N}{X} \rceil \times T$ を出力
提出コード

void solve(){
    int N, X, T;
    cin >> N >> X >> T;
    cout << (N + X - 1) / X * T << endl;
}

B - Multiple of 9

桁和を求めてあげればいい
pythonだとそのままでいけるっぽい
提出コード

void solve(){
    string S;
    cin >> S;
    ll sum = 0;
    REP(i,size(S)) sum += (S[i] - '0');
    if(sum % 9 == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

C - Step

前からmaxを更新していく
$max \gt A_i$ のときその差分を加算していく
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];
    ll ma = A[0];
    ll sum = 0;
    for(int i=1;i<N;i++){
        if(ma > A[i]) sum += ma - A[i];
        chmax(ma, A[i]);
    }
    cout << sum << endl;
}

D - Wizard in Maze

BFSしようとしたらWAが生えたのでdijkstraで通した(落ちるケースあるのかな）
BFSの場合01BFSでいいっぽい
提出コード(dijkstra)

void solve(){
    int H, W, Ch, Cw, Dh, Dw;
    cin >> H >> W >> Ch >> Cw >> Dh >> Dw;
    Ch--, Cw--, Dh--, Dw--;
    vector<string> S(H);
    REP(i,H) cin >> S[i];
    vector<vector<ll>> dist(H, vector<ll>(W, LINF));
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<tuple<ll, int, int>>> q;
    q.emplace(0, Ch, Cw);
    dist[Ch][Cw] = 0;
    while(!q.empty()){
        auto [d, h, w] = q.top(); q.pop();
        if(dist[h][w] < d) continue;
        if(h == Dh and w == Dw) break;
        for(int i=-2;i<=2;i++) for(int j=-2;j<=2;j++){
            int nh = h + i, nw = w + j;
            if(nh < 0 or nh >= H or nw < 0 or nw >= W) continue;
            if(S[nh][nw] == '#') continue;
            if(abs(nh - h) + abs(nw - w) >= 2){
                if(dist[nh][nw] > d + 1){
                    dist[nh][nw] = d + 1;
                    q.emplace(d+1,nh, nw);
                }
            }
            else{
                if(nh < 0 or nh >= H or nw < 0 or nw >= W) continue;
                if(S[nh][nw] == '#') continue;
                if(dist[nh][nw] > d){
                    dist[nh][nw] = d;
                    q.emplace(d, nh, nw);
                }
            }
        }
    }
    ll ans = dist[Dh][Dw];
    if(ans == LINF) ans = -1;
    cout << ans << endl;
}

提出コード(01BFS)

void solve(){
    int H, W, Ch, Cw, Dh, Dw;
    cin >> H >> W >> Ch >> Cw >> Dh >> Dw;
    Ch--, Cw--, Dh--, Dw--;
    vector<string> S(H);
    REP(i,H) cin >> S[i];
    vector<vector<ll>> dist(H, vector<ll>(W, LINF));
    deque<tuple<ll, int, int>> dq;
    dq.emplace_back(0, Ch, Cw);
    dist[Ch][Cw] = 0;
    while(!dq.empty()){
        auto [d, h, w] = dq.front(); dq.pop_front();
        if(dist[h][w] < d) continue;

        for(int i=-2;i<=2;i++) for(int j=-2;j<=2;j++){
            int nh = h + i, nw = w + j;
            if(nh < 0 or nh >= H or nw < 0 or nw >= W) continue;
            if(S[nh][nw] == '#') continue;
            if(abs(nh - h) + abs(nw - w) >= 2){
                if(dist[nh][nw] > d + 1){
                    dist[nh][nw] = d + 1;
                    dq.emplace_back(d+1,nh, nw);
                }
            }
            else{
                if(nh < 0 or nh >= H or nw < 0 or nw >= W) continue;
                if(S[nh][nw] == '#') continue;
                if(dist[nh][nw] > d){
                    dist[nh][nw] = d;
                    dq.emplace_front(d, nh, nw);
                }
            }
        }
    }
    ll ans = dist[Dh][Dw];
    if(ans == LINF) ans = -1;
    cout << ans << endl;
}

E - Bomber

想定解が頭良かった
想定解は縦方向の最大と横方向の最大の組み合わせのみ調べればいい
縦方向と横方向の片方を固定して頑張る
縦か横方向のどちらかはどれかの爆弾を通っているので各爆弾の縦方向を固定、横方向を固定したときのmaxを更新していく
縦hを固定したときに、横方向wのmaxを加算する
この時、 $(h, w)$ に爆弾がある時、重複分を $-1$ する
提出コード

void solve(){
    int H, W, M;
    cin >> H >> W >> M;
    vector<int> h(M), w(M);
    vector<int> A(303030), B(303030);
    set<P> stA, stB;
    set<P> st;
    REP(i,M){
        cin >> h[i] >> w[i];
        A[h[i]]++;
        B[w[i]]++;
        st.insert(make_pair(h[i], w[i]));
    }
    REP(i,303030) stA.insert(make_pair(A[i], i));
    REP(i,303030) stB.insert(make_pair(B[i], i));
    int ans = 0;
    REP(i,M){
        int hh = A[h[i]];
        auto itr = stB.rbegin();
        auto [v, idx] = *itr;
        if(st.find(P(h[i], idx)) != st.end()) chmax(ans, hh + v - 1);
        else chmax(ans, hh + v);
        int ww = B[w[i]];
        auto itr2 = stA.rbegin();
        auto [v2, idx2] = *itr2;
        if(st.find(P(idx2, w[i])) != st.end()) chmax(ans, ww + v2 - 1);
        else chmax(ans, ww + v2);
    }
    cout << ans << endl;
}

提出コード

void solve(){
    int H, W, M;
    cin >> H >> W >> M;
    vector<int> h(M), w(M);
    vector<int> A(303030), B(303030);
    int maA = 0, maB = 0;;
    set<P> st;
    REP(i,M){
        cin >> h[i] >> w[i];
        A[h[i]]++;
        chmax(maA, A[h[i]]);
        B[w[i]]++;
        chmax(maB, B[w[i]]);
        st.insert(make_pair(h[i], w[i]));
    }
    vector<int> candA, candB;
    REP(i,303030){
        if(A[i] == maA) candA.emplace_back(i);
        if(B[i] == maB) candB.emplace_back(i);
    }
    for(auto a : candA) for(auto b : candB){
        if(st.find(P(a, b)) == st.end()){
            cout << maA + maB << endl;
            return;
        }
    }
    cout << maA + maB - 1 << endl;
}