AtCoder Beginner Contest 244（ABC244）

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 244での成績：375位
パフォーマンス：1747相当
レーティング：1536→1559 (+23) :)#AtCoder #ABC244 https://t.co/pdjtQvwnsD

— ボンド@競プロ (@bond_cmprog) March 20, 2022

A - Last Letter

S.back()を出力

提出コード

void solve(){
    int N;
    string S;
    cin >> N >> S;
    cout << S.back() << endl;
}

B - Go Straight and Turn Right

今見ている方向を管理する

提出コード

void solve(){
    int N;
    string T;
    cin >> N >> T;
    int x = 0;
    int y = 0;
    int dir = 0;
    const int dx[4] = {1, 0, -1, 0};
    const int dy[4] = {0, -1, 0, 1};
    for(char c : T){
        if(c == 'S'){
            x += dx[dir];
            y += dy[dir];
        }
        else{
            dir = (dir + 1) % 4;
        }
    }
    cout << x << " " << y << endl;
}

C - Yamanote Line Game

すでに使った整数を管理しておき、答えるときにはまだ使っていないものをどれか一つ出力する

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> used(2*N+1, 0);
    while(1){
        REP(i,2*N+1) if(!used[i]){
            cout << i + 1 << endl;
            used[i] = 1;
            break;
        }
        int x;
        cin >> x;
        if(x == 0){
            break;
        }
        else{
            used[x-1] = 1;
        }
    }
}

D - Swap Hats

SとTの転倒数を求める
転倒数の偶奇が異なる場合、操作は偶数回しか行えないのでNoとなる

提出コード

void solve(){
    vector<char> S(3), T(3);
    REP(i,3) cin >> S[i];
    REP(i,3) cin >> T[i];

    int inv = inversionNumber(S, T);
    if(inv == -1 or inv % 2 == 1) cout << "No" << endl;
    else cout << "Yes" << endl;
}

E - King Bombee

$ dp[i][j][k] := i $ 回目の移動のときに頂点 $ j $ にいて、$ X $ が $ k \pmod{2} $ 回出現しているときの場合の数としてDPを行う

提出コード

void solve(){
    int N, M, K, S, T, X;
    cin >> N >> M >> K >> S >> T >> X;
    --X, --S, --T;
    vector<vector<int>> g(N);
    REP(i,M){
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vector dp(K+1, vector(N, vector<mint>(2, 0)));
    dp[0][S][0] = 1;
    REP(i,K){
        REP(j,N){
            for(int nv : g[j]){
                REP(k,2){
                    if(nv == X){
                        dp[i+1][nv][k^1] += dp[i][j][k];
                    }
                    else dp[i+1][nv][k] += dp[i][j][k];
                }
            }
        }
    }
    cout << dp[K][T][0] << endl;
}

F - Shortest Good Path

$ dist[S][i] := $ 各頂点を通った回数が偶数か奇数かの状態 $ S $ のときに、最後に訪れた頂点が $ i $ のときの最短経路としてBFSを行う

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<vector<int>> g(N);
    REP(i,M){
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vector dist(1<<N, vector(N, LINF));
    queue<tuple<int, int, int>> q;
    REP(i,N){
        dist[1<<i][i] = 1;
        q.emplace(1<<i, i, 1);
    }
    while(!q.empty()){
        auto [bits, v, d] = q.front(); q.pop();
        for(int nv : g[v]){
            if(chmin(dist[bits^(1<<nv)][nv], dist[bits][v] + 1)) q.emplace(bits^(1<<nv), nv, dist[bits^(1<<nv)][nv]);
        }
    }
    ll ans = 0;
    REP(i,1,1<<N){
        ll mi = LINF;
        REP(j,N) chmin(mi, dist[i][j]);
        ans += mi;
    }
    cout << ans << endl;
}