ABC 264 参加記

参加記を書くのをサボっていたのですが、freee プログラミングコンテスト2022（AtCoder Beginner Contest 264）で学生順位100位で賞金を頂けたので書きます。 初めての賞金です、うれしい！！！

73分6完で273位、パフォーマンスは2108でした。

A “atcoder”.substr()

問題

文字列atcoderの$L$文字目から$R$文字目までを出力してね

  • $1 \leq L \leq R \leq 7$

提出コード

int main(){
 
    string a = "atcoder";
 
    LL(L, R); L--; 
 
    string ans = "";
    for(auto i = L; i < R; i++) ans += a[i];
    OUT(ans);
 
}

B Nice Grid

問題

ここを読んでね

提出コード

vs A = {
    "xxxxxxxxxxxxxxx",
    "xooooooooooooox",
    "xoxxxxxxxxxxxox",
    "xoxoooooooooxox",
    "xoxoxxxxxxxoxox",
    "xoxoxoooooxoxox",
    "xoxoxoxxxoxoxox",
    "xoxoxoxoxoxoxox",
    "xoxoxoxxxoxoxox",
    "xoxoxoooooxoxox",
    "xoxoxxxxxxxoxox",
    "xoxoooooooooxox",
    "xoxxxxxxxxxxxox",
    "xooooooooooooox",
    "xxxxxxxxxxxxxxx",
};
 
int main(){
 
    LL(R, C); R--; C--;
 
    if (A[R][C] == 'x') OUT("black");
    else OUT("white");
 
}

C Matrix Reducing

問題

$H_1$行$W_1$列の行列$A$と、$H_2$行$W_2$列の$B$が与えられます。

  • $1 \leq i \leq H_1$ かつ $1 \leq j \leq W_1$ について、行列 $A$ の $i$行目 $j$列目の要素は $A_{i, j}$です。
  • $1 \leq i \leq H_2$ かつ $1 \leq j \leq W_2$ について、行列 $B$ の $i$行目 $j$列目の要素は $B_{i, j}$です。

行列 $A$に対して、下記の2つの操作のうちどちらかを行うことを、好きなだけ繰り返すことができます。

  • $A$の行を任意に$1$つ選んで削除する。
  • $A$の列を任意に$1$つ選んで削除する。

行列 $A$ を行列 $B$ に一致させることができるかどうかを判定してください。

  • $1 \leq H_2 \leq H_1 \leq 10$
  • $1 \leq W_2 \leq W_2 \leq 10$
  • $1 \leq A_{i, j}, B_{i, j} \leq 10^9$

考察

$H, W$が小さいので、各行/列を消す/消さないのbit全探索を行えばよいです。

提出コード

int main(){
 
    LL(H1, W1);
    vvll A(H1, vll(W1));
    rep(i, H1) rep(j, W1) cin >> A[i][j];
 
    LL(H2, W2);
    vvll B(H2, vll(W2));
    rep(i, H2) rep(j, W2) cin >> B[i][j];
 
    bool ans = false;
 
    rep(bith, 1 << H1) rep(bitw, 1 << W1) {
        vvll C;
        rep(i, H1) if ((bith >> i) & 1) {
            vll c;
            rep(j, W1) if ((bitw >> j) & 1) c.pb(A[i][j]);
            C.pb(c);
        }
        if (C == B) ans = true;
    }
 
    YesNo(ans);
 
}

D “redocta”.swap(i, i+1)

問題

atcoder の並び替えである文字列 $S$が与えられます。隣接する2文字を入れ替える操作を行ってatcoderにするために必要な最小の操作回数はいくつですか？

考察

転倒数を知っていますか？　僕は知っています。

提出コード

int main(){
 
    STR(S);
 
    string a = "atcoder";
 
    map<char, int> U;
    rep (i, a.size()) U[a[i]] = i;
 
    ll ans = 0;
    rep (i, S.size()) {
        rep (j, i) {
            if (U[S[j]] > U[S[i]]) ans++;
        }
    }
 
    OUT(ans);
 
}

E Blackout 2

問題

$N$個の都市と$M$個の発電所があります。また、電線が$E$本あり、電線$i$は$U_i$と$V_i$を双方向に結びます。 また、ある都市に電気が通っているとは、ある年から電線をいくつかたどって少なくとも一つの発電所にたドりつける状態を言います。 $Q$個のイベントが起こります。$i$番目のイベントでは電線$X_i$が切れ、その電線をたどることができなくなります。一度切れた電線は、その後のイベントにおいても切れたままです。 すべてのイベントについて、そのイベントが終わった直後に電気が通っている都市の数を求めてください。

  • $1 \leq N + M \leq 2 \times 10 ^ 5$
  • $1 \leq Q \leq E \leq 5 \times 10 ^ 5$
  • $1 \leq U_i < V_i \leq N + M$
  • $i \neq j$ならば$U_i \neq U_j$または$V_i \neq V_j$
  • $1 \leq X_i \leq E$, $X_i$は相異なる

考察

　 問題文に逆から見てねと書いてあるので逆から見ます。適当にBFSみたいなことをしてしまいましたが、 UnionFindを使うと実装が楽になります。 また、発電所を1つとみなすと見通しがよくなります。両方思い浮かびませんでした…

提出コード


int main(){
 
    LL(N, M, E);
    vector<pll> Edge;
    rep (i, E) {
        LL(a, b); a--; b--;
        Edge.pb({a, b});
    }
    LL(Q);
    vll Query;
    set<ll> X;
    rep (i, Q) {
        LL(a); a--;
        Query.pb(a);
        X.insert(a);
    }
 
    vvll G(N+M);
    rep (i, E){ 
        if (X.find(i) == X.end()) {
            G[Edge[i].fi].pb(Edge[i].se);
            G[Edge[i].se].pb(Edge[i].fi);
        }
    }    
 
    vb elec(N + M, false);
    ll ans = 0;
 
    deque<ll> que;
    for(int m = N; m < N + M; m++) que.pb(m);
 
    while (!que.empty()) {
        ll v = que.front(); que.pop_front();
        if (elec[v]) continue;
        elec[v] = true;
        if (v < N) ans++;
        for (auto u: G[v]) {
            if (elec[u]) continue;
            que.pb(u);
        }
    }
 
    vll Ans; Ans.pb(ans);
 
    reverse(all(Query));
 
    for (auto x: Query) {
 
        G[Edge[x].fi].pb(Edge[x].se);
        G[Edge[x].se].pb(Edge[x].fi);
 
        deque<ll> que;
        if (elec[Edge[x].fi]) que.pb(Edge[x].se);
        if (elec[Edge[x].se]) que.pb(Edge[x].fi);
 
        while (!que.empty()) {
            ll v = que.front(); que.pop_front();
            if (elec[v]) continue;
            elec[v] = true;
            if (v < N) ans++;
            for (auto u: G[v]) {
                if (elec[u]) continue;
                que.pb(u);
            }
        }
 
        Ans.pb(ans);
 
    }
    
    Ans.pop_back();
    reverse(all(Ans));
    for(auto a: Ans) OUT(a);
 
}

F Monochromatic Path

問題

各マスが白または黒で塗られた$H$行$W$列のグリッドがあります。$1 \leq i \leq H$かつ$1 \leq j \leq W$を満たす整数の組$(i, j)$について、 グリッドの上から$i$行目、左から$j$行目のマスの色は$A_{i, j}$で表されます。$0$の時は白、$1$の時は黒です。 次の2つの操作のどちらかを行うことを好きなだけ繰り返すことができます。

  • $1 \leq i \leq H$を満たす整数を選び、$R_i$円払った後グリッドの上から$i$行目にあるそれぞれのマスを反転させる。
  • $1 \leq j \leq W$を満たす整数を選び、$C_j$円払った後グリッドの左から$j$列目にあるそれぞれのマスを反転させる。 マス$(1, 1)$から$(H, W)$まで、現在いるマスの右もしくは下にあるマスに移動する経路であって、通るマスの色がすべて同じようになるようなもののうち、かかる費用の最小を出力してください。
  • $2 \leq H, W \leq 2000$
  • $1 \leq R_i, C_j \leq 10^9$

考察

dp[x][y][i][j] := $(x, y)$まで行く最小のコスト($i = 1$ならば$x$行が反転、$j = 1$ならば$y$が反転)としてDPをすると解けます。 $(x, y)$にいるとき、それ以前の行/列をどう反転したかには興味がないため、今いる行/列が反転しているかどうかを見ればよいです。

提出コード

int main(){
 
    LL(H, W);
    VEC(ll, R, H);
    VEC(ll, C, W);
    VEC(string, A, H);
 
    vector dp(vector (H+1, vector(W+1, vector(2, vector(2, INF)))));
    dp[0][0][0][0] = 0;
    dp[0][0][1][0] = R[0];
    dp[0][0][0][1] = C[0];
    dp[0][0][1][1] = R[0] + C[0];
 
    rep(i, H) rep(j, W) rep(iinv, 2) rep(jinv, 2) {
        int n = (A[i][j] == '0' ? 0 : 1);   // 今のi, j
        n += iinv + jinv; n %= 2;
 
        if (i + 1 < H) {
            int x = (A[i+1][j] == '0' ? 0 : 1); // 行き先のi, j 
            x += jinv; x %= 2;
            if (n == x) {
                chmin(dp[i+1][j][0][jinv], dp[i][j][iinv][jinv]);
            } else {
                chmin(dp[i+1][j][1][jinv], dp[i][j][iinv][jinv] + R[i+1]);
            }
        }
 
        if (j + 1 < W) {
            int x = (A[i][j+1] == '0' ? 0 : 1);
            x += iinv; x %= 2;
            if (n == x) {
                chmin(dp[i][j+1][iinv][0], dp[i][j][iinv][jinv]);
            } else {
                chmin(dp[i][j+1][iinv][1], dp[i][j][iinv][jinv] + C[j+1]);
            }
        }
 
    }
 
    ll ans = INF;
    rep(x, 2) rep(y, 2) chmin(ans, dp[H-1][W-1][x][y]);
 
    OUT(ans); 
 
}

DPで解けそうということに早い段階で気づけたのでだいぶ良かったです。成長…！

Comment is disabled to avoid unwanted discussions from 'localhost:1313' on your Disqus account...

Theme Name