接着剤の精進日記

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

AtCoder Beginner Contest 197(ABC197)

atcoder.jp

A - Rotate

$ S[1]S[2]S[0] $ を出力
提出コード

void solve(){
    string S;
    cin >> S;
    cout << S[1] << S[2] << S[0] << endl;
}

B - Visibility

マス $ (X, Y) $ から上下左右に#にぶつかるまでのマスの個数を数える
提出コード

void solve(){
    int H, W, X, Y;
    cin >> H >> W >> X >> Y;
    X--,Y--;
    vector<string> S(H);
    REP(i,H) cin >> S[i];
    int ans = 1;
    for(int i=X+1;i<H;i++){
        if(S[i][Y] == '#') break;
        ans++;
    }
    for(int i=X-1;i>=0;i--){
        if(S[i][Y] == '#') break;
        ans++;
    }
    for(int i=Y+1;i<W;i++){
        if(S[X][i] == '#') break;
        ans++;
    }
    for(int i=Y-1;i>=0;i--){
        if(S[X][i] == '#') break;
        ans++;
    }
    cout << ans << endl;
}

C - ORXOR

どの箇所に仕切りを入れるかどうかをbit全探索をする
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];
    ll ans = LINF;
    REP(i,1<<N){
        ll cur = 0;
        ll sum = 0;
        REP(j,N){
            cur |= A[j];
            if(i >> j & 1){
                sum ^= cur;
                cur = 0;
            }
        }
        sum ^= cur;
        chmin(ans, sum);
    }
    cout << ans << endl;
}

D - Opposite

正 $ N $ 角形の中心 $ (x, y) $を考える
$ (x, y) = \left(\frac{x_0 + x_{\frac{N}{2}}}{2}, \frac{y_0 + y_{\frac{N}{2}}}{2} \right)$ となるので、$ (x_0 - x, y_0 - y) $ として(x, y)を原点とした時の $ (x_0, y_0) $ を考える
この時、$ (x_1, y_1) $ は $ (x_0, y_0) $ を $ \theta = \frac{2\pi}{N} $ だけ原点を中心に回転させたものとなる
あとはこの座標を求めたあとにもとの座標に戻して上げればいい
提出コード

void solve(){
    double N;
    cin >> N;
    double x0, y0, x2, y2;
    cin >> x0 >> y0 >> x2 >> y2;
    double x = (x2 + x0) / 2.0;
    double y = (y2 + y0) / 2.0;
    double x1 = x + (x0 - x)*cos(2.0*PI/N) - (y0 - y)*sin(2.0*PI/N);
    double y1 = y + (x0 - x)*sin(2.0*PI/N) + (y0 - y)*cos(2.0*PI/N);
    printf("%.12lf %.12lf\n", x1, y1);
}

E - Traveler

色 $ i $ のボールをすべて取り終わったときにどこにいるかを考えると色 $ i $ のボールが置いてある最小の座標と最大の座標のどちらかであるのでその2つのみを考えればいい
そのため次のようなDPを考えればいい
$ dp[i][j] := $ 色 $ i $ のボールをすべて取り終わったときに一番左端 $ (j=0) $ にいる、一番右端にいる$ (j=1) $ ときの最小のコストとしてDPをする
提出コード

void solve(){
    ll N;
    cin >> N;
    vector<ll> X(N), C(N);
    map<ll, vector<ll>> mp;
    Compress<ll> cmp;
    cmp.add(0);
    REP(i,N){
        cin >> X[i] >> C[i];
        cmp.add(C[i]);
    }
    cmp.build();
    REP(i,N) mp[cmp.get(C[i])].emplace_back(X[i]);
    for(auto &[k, v] : mp){
        sort(v.begin(), v.end());
    }
    mp[0].emplace_back(0);
    auto f = [&](ll a, ll b) -> ll{
        return abs(a - b);
    };
    int sz = mp.size();
    vector<vector<ll>> dp(sz+1, vector<ll>(2, LINF));
    dp[0][0] = dp[0][1] = 0;
    for(int i=1;i<sz;i++){
        auto curMi = mp[i].front();
        auto curMa = mp[i].back();
        auto preMi = mp[i-1].front();
        auto preMa = mp[i-1].back();
        ll dist = f(curMa, curMi);
        chmin(dp[i][0], dp[i-1][0] + f(preMi, curMa) + dist); // mi -> ma -> mi
        chmin(dp[i][0], dp[i-1][1] + f(preMa, curMa) + dist); // ma -> ma -> mi
        chmin(dp[i][1], dp[i-1][0] + f(preMi, curMi) + dist); // mi -> mi -> ma
        chmin(dp[i][1], dp[i-1][1] + f(preMa, curMi) + dist); // ma -> mi -> ma
    }
    cout << min(dp[sz-1][0] + abs(mp[sz-1].front()), dp[sz-1][1]+abs(mp[sz-1].back())) << endl;
}

F - Construct a Palindrome

頂点 $ 1 $ と 頂点 $ N $ に置かれた2つのコマが同じ文字の辺を通って合流もしくは隣接した頂点にたどり着くことを考える
$ dist[a][b] := a $ と $ b $ にそれぞれコマがある状態で、かつ同じ文字の辺を通ってきた状態での最短距離としてbfsなどで求める
そうすると偶数長の場合は最終的に同じ頂点にいるので $ 2 \times dist[i][i] $ の最小、奇数長の場合、隣接した頂点にいるので 頂点 $ i $ と辺で繋がっている頂点を $ nv $ とすると $ 2 \times dp[i][nv] + 1 $ の最小が答えとなる
提出コード

    int N, M;
    cin >> N >> M;
    vector<vector<pair<int, int>>> edge(N);
    REP(i,M){
        int a, b;
        char c;
        cin >> a >> b >> c;
        --a, --b;
        edge[a].emplace_back(b, c-'a');
        edge[b].emplace_back(a, c-'a');
    }
    vector dist(N, vector(N, INF));
    dist[0][N-1] = 0;
    queue<pair<int, int>> q;
    q.emplace(0, N-1);
    while(!q.empty()){
        auto [a, b] = q.front(); q.pop();
        for(auto [na, c1] : edge[a]) for(auto [nb, c2] : edge[b]){
            if(c1 != c2) continue;
            if(dist[na][nb] < INF) continue;
            dist[na][nb] = dist[a][b] + 1;
            q.emplace(na, nb);
        }
    }
    int ans = INF;
    REP(i,N){
        chmin(ans, dist[i][i] * 2);
        for(auto [nv, c] : edge[i]){
            chmin(ans, dist[i][nv] * 2 + 1);
        }
    }
    if(ans == INF) ans = -1;
    cout << ans << endl;
}