AtCoder Beginner Contest 211（ABC211）

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 211での成績：461位
パフォーマンス：1841相当
レーティング：1432→1480 (+48) :)#AtCoder #ABC211 https://t.co/35eVrZ6yqx

— ボンド@競プロ (@bond_cmprog) July 24, 2021

A - Blood Pressure

問題文のとおりに出力
提出コード

void solve(){
    double A, B;
    cin >> A >> B;
    printf("%.12lf\n", (A - B) / 3 + B);
}

B - Cycle Hit

入力が4通りしか存在しないのでsetで判定する
提出コード

void solve(){
    set<string> st;
    REP(i,4){
        string s;
        cin >> s;
        st.insert(s);
    }
    if(st.size() == 4) cout << "Yes" << endl;
    else cout << "No" << endl;
}

C - chokudai

$ dp[i][j] := i $ 文字目まで見たときにchokudaiの $ j $ 文字目まで作ることができる場合の数としてDPする
提出コード

void solve(){
    string S;
    cin >> S;
    int sz = S.size();
    string chokudai = "chokudai";
    vector dp(sz+1, vector<mint>(9, 0));
    dp[0][0] = 1;
    REP(i,sz){
        REP(j,9){
            dp[i+1][j] += dp[i][j];
            if(j < 8 and S[i] == chokudai[j]) dp[i+1][j+1] += dp[i][j];
        }
    }
    cout << dp[sz][8] << endl;
}

D - Number of Shortest paths

bfsなどで最短経路を求める最中にDPでその経路の数も一緒に数える
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<vector<int>> g(N);
    REP(i,M){
        int a, b;
        cin >> a >> b;
        g[--a].emplace_back(--b);
        g[b].emplace_back(a);
    }
    vector<int> dist(N, INF);
    vector<mint> dp(N, 0);
    dp[0] = 1;
    dist[0] = 0;
    priority_queue<P, vector<P>, greater<P>> pq;
    pq.emplace(0, 0);
    while(!pq.empty()){
        auto [d, cur] = pq.top(); pq.pop();
        if(dist[cur] < d) continue;
        for(auto nv : g[cur]){
            if(dist[nv] > dist[cur] + 1){
                dist[nv] = dist[cur] + 1;
                pq.emplace(dist[nv], nv);
                dp[nv] = dp[cur];
            }
            else if(dist[nv] == dist[cur] + 1) dp[nv] += dp[cur];
        }
    }
    cout << dp[N-1] << endl;
}

E - Red Polyomino

条件を満たす塗り方の個数は少ないので全探索をする
マスを赤く塗る残り回数を $ k $、マス目を赤に塗ったかどうかを表す状態を $ state $ として、$ set[k] $ を使ってすでに調べた状態を管理する
ある状態 $ state $ が与えられたとき、赤く塗られたマスのどれかを選び、その上下左右のマスを塗るかどうかをdfsなどで全探索していく
提出コード

using ull = unsigned ll;

void solve(){
    int N, K;
    cin >> N >> K;
    vector<string> fi(N);
    REP(i,N) cin >> fi[i];
    set<ull> st[8];
    auto encode = [&](int h, int w) -> ull{
        return h * N + w;
    };
    auto dfs = [&](auto && self, int k, ull state) -> void{
        if(k == 0){
            st[k].insert(state);
            return;
        }
        if(st[k].count(state)) return;
        st[k].insert(state);
        for(ull i=0;i<64;i++) if(state >> i & 1){
            int h = i / N;
            int w = i % N;
            REP(d,4){
                int nh = h + dx[d];
                int nw = w + dy[d];
                if(nh < 0 or nh >= N or nw < 0 or nw >= N or fi[nh][nw] == '#') continue;
                if(state >> encode(nh, nw) & 1) continue;
                self(self, k-1, state | (1uLL << encode(nh, nw)));
            }
        }
    };
    REP(i,N) REP(j,N) if(fi[i][j] == '.'){
        dfs(dfs, K-1, (1ull << encode(i, j)));
    }
    cout << st[0].size() << endl;
}