AtCoder Beginner Contest 232（ABC232）

atcoder.jp

黄パフォ久々
Bondo416さんのM-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232)での成績：270位
パフォーマンス：2021相当
レーティング：1457→1528 (+71) :)#AtCoder #M-SOLUTIONSプロコンオープン2021(ABC232) https://t.co/ciAnCVKhUs

— ボンド@競プロ (@bond_cmprog) December 19, 2021

A - QQ solver

$ S_0 \times S_2 $ を出力

提出コード

void solve(){
    string s;
    cin >> s;
    cout << (s[0] - '0') * (s[2] - '0') << endl;
}

B - Caesar Cipher

$ S_i $ から $ T_i $ にするための操作回数を求める
これらの操作回数がすべて同一ならYes

提出コード

void solve(){
    string S, T;
    cin >> S >> T;
    set<int> st;
    REP(i,S.size()){
        char c = S[i];
        int cur = 0;
        REP(_,26){
            if(c == T[i]) break;
            if(c == 'z') c = 'a';
            else c++;
            cur++;
        }
        st.insert(cur);
    }
    if(st.size() == 1) cout << "Yes" << endl;
    else cout << "No" << endl;
}

C - Graph Isomorphism

next_permutationで条件を満たす $ P $ が存在するかを全探索する

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> A(M), B(M), C(M), D(M);
    vector<vector<int>> taka(N, vector<int>(N));
    auto aoki = taka;
    REP(i,M){
        cin >> A[i] >> B[i];
        --A[i], --B[i];
        taka[A[i]][B[i]] = taka[B[i]][A[i]] = 1;
    }
    REP(i,M){
        cin >> C[i] >> D[i];
        --C[i], --D[i];
        aoki[C[i]][D[i]] = aoki[D[i]][C[i]] = 1;
    }
    vector<int> P(N);
    iota(ALL(P), 0);
    do{
        bool ok = true;
        REP(i,N) REP(j,i+1,N){
            if(taka[i][j] != aoki[P[i]][P[j]]) ok = false;
        }
        if(ok){
            cout << "Yes" << endl;
            return;
        }
    }while(next_permutation(ALL(P)));
    cout << "No" << endl;
}

D - Weak Takahashi

$ (1, 1) $ からの各マスへの最短経路の最長を求めればいい

提出コード

void solve(){
    int H, W;
    cin >> H >> W;
    vector<string> C(H);
    REP(i,H) cin >> C[i];
    vector dist(H, vector(W, INF));
    queue<tuple<int, int, int>> q;
    dist[0][0] = 1;
    q.emplace(1, 0, 0);
    while(!q.empty()){
        auto [d, h, w] = q.front(); q.pop();
        REP(d,2){
            int nh = h + dx[d];
            int nw = w + dy[d];
            if(nh < 0 or nh >= H or nw < 0 or nw >= W or C[nh][nw] == '#') continue;
            if(dist[nh][nw] < INF) continue;
            dist[nh][nw] = dist[h][w] + 1;
            q.emplace(dist[nh][nw], nh, nw);
        }
    }
    int ans = 0;
    REP(i,H) REP(j,W) if(dist[i][j] < INF) chmax(ans, dist[i][j]);
    cout << ans << endl;
}

E - Rook Path

$ dp[i][j][k] := k $ 回操作を行ったときに、$ x_2 $ と同じ行にいるかどうか $ (i) $ 、$ y_2 $ と同じ列にいるかどうか $ (j) $ としてDPを行う

提出コード

void solve(){
    ll H, W, K;
    cin >> H >> W >> K;
    ll x, y, x2, y2;
    cin >> x >> y >> x2 >> y2;
    vector dp(2, vector(2, vector<mint>(K+1, 0)));
    dp[x==x2][y==y2][0] = 1;
    REP(k,K){
        if(dp[0][0][k] != 0){
            // (0,0) -> (0, 0)
            dp[0][0][k+1] += dp[0][0][k] * (H - 2 + W - 2);
            // (0,0) -> (1, 0)
            dp[1][0][k+1] += dp[0][0][k];
            // (0,0) -> (0, 1)
            dp[0][1][k+1] += dp[0][0][k];
        }
        if(dp[1][0][k] != 0){
            // (1,0) -> (0, 0)
            dp[0][0][k+1] += dp[1][0][k] * (H - 1);
            // (1,0) -> (1, 0)
            dp[1][0][k+1] += dp[1][0][k] * (W - 2);
            // (1,0) -> (1, 1)
            dp[1][1][k+1] += dp[1][0][k];

        }
        if(dp[0][1][k] != 0){
            // (0,1) -> (0, 0)
            dp[0][0][k+1] += dp[0][1][k] * (W - 1);
            // (0,1) -> (0, 1)
            dp[0][1][k+1] += dp[0][1][k] * (H - 2);
            // (1,0) -> (1, 1)
            dp[1][1][k+1] += dp[0][1][k];
        }
        if(dp[1][1][k] != 0){
            // (1,1) -> (1, 0)
            dp[1][0][k+1] += dp[1][1][k] * (W - 1);
            // (1,1) -> (0, 1)
            dp[0][1][k+1] += dp[1][1][k] * (H - 1);
        }
    }
    cout << dp[1][1][K] << endl;
}

F - Simple Operations on Sequence

$ dp[state] := state $ で立っているbitが左端にソートされた状態にするための最小費用としてDPを行う

提出コード

void solve(){
    ll N, X, Y;
    cin >> N >> X >> Y;
    vector<ll> A(N), B(N);
    REP(i,N) cin >> A[i];
    REP(i,N) cin >> B[i];
    vector dp(1<<N, LINF);
    dp[0] = 0;
    REP(s,1<<N) REP(i,N){
        if(s >> i & 1) continue;
        ll cur = 0;
        REP(j,i) if(!(s >> j & 1)) cur++;
        int idx = __builtin_popcount(s);
        chmin(dp[s|(1<<i)], dp[s] + abs(B[idx] - A[i]) * X + cur * Y);
    }
    cout << dp[(1<<N)-1] << endl;
}