AtCoder Beginner Contest 282

HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282) - AtCoder

結果

A - Generalized ABC:AC(1:26)
B - Let's Get a Perfect Score:AC(42:26)
C - String Delimiter:AC(53:34)
D - Make Bipartite 2:提出無し

A - Generalized ABC

整数$${K}$$が与えられ、英大文字をAから順に$${K}$$個出力する問題

自分の回答

int main(){
  int K;
  cin >> K;
  for(int i = 0; i < K; i++){
    printf("%c", 65 + i);
  }
  printf("\n");
}

charの仕様を使って終わり

公式解説

省略

B - Let's Get a Perfect Score

1から$${N}$$番までの番号が付いた参加者が$${M}$$問からなるコンテストに参加する
$${S_{i,j}}$$が「o」のとき$${i}$$番の人が問題$${j}$$を解け、「x」のとき解くことができない
ペアを組んで問題を解き、全ての問題において少なくとも一方が解くことができるペアが何組あるかを求める問題

自分の回答

int main(){
  int N, M;
  cin >> N >> M;
  vector<string> S(N);
  for(int i = 0; i < N; i++){
    cin >> S[i];
  }
 
  int ans = 0;
  for(int i = 0; i < N - 1; i++){
    for(int j = i + 1; j < N; j++){
      for(int k = 0; k < M; k++){
        if(S[i][k] == 'x' && S[j][k] == 'x'){
          goto NEXT;
        }
      }
      ans++;
      NEXT:;
    }
  }
  printf("%d\n", ans);
}

そのまま

最初ビットでやろうと思ったけど入力をビットへ変換するのが大変だったからこの方法で書いた
最初いろいろやっているうちにだいぶ時間消費してしまった

公式解説

省略

C - String Delimiter

英小文字、「,」「"」からなる長さ$${N}$$の文字列が与えられ、奇数個目の「"」とその次に出てくる「"」の間にある文字列を「括られた文字列」とする
$${S}$$の括られていない「,」を「.」にして出力する問題

自分の回答

int main(){
  int N;
  cin >> N;

  bool srr = false;
  for(int i = 0; i < N; i++){
    char c;
    cin >> c;
    if(c == '"'){
      srr = !srr;
    }
    if(!srr && c == ','){
      printf(".");
    }
    else{
      printf("%c", c);
    }
  }
  printf("\n");
}

括られているかはboolのフラグを立てて「"」が出たら反転することで判断
後は先頭から見て行って括られていない時に「,」が出たら「.」にして出力するだけ

この問題解いている時に気付いたけどVSCodeの構文チェックが機能していなくて再インストールするまで何しても動かなかったから割と不便だった

公式解説

省略

D - Make Bipartite 2

$${N}$$個の頂点と$${M}$$本の辺からなる単純無向グラフ$${G}$$が与えられ、$${i}$$番目の辺は頂点$${u_{i}}$$と$${v_{i}}$$を結んでいる
グラフ$${G}$$において、二部グラフ(各頂点が黒か白で塗られ、同じ色の頂点を結ぶ辺が存在しないグラフ)として成立する辺をあと何本引けるかを求める問題

自分の回答

初期状態の色分けは幅優先探索でいいとして後は異なる色で辺が無い頂点がいくつあるかを求めればいいんだろうけどどう管理して計算するかを思いつかなかった

公式解説

typedef long long ll;
typedef pair<ll, ll> P;

ll n, m;
vector<int> G[200005];
int color[200005];
P dfs(int v, int p, int c){
  P ret = P(0, 0);
  color[v] = c;
  
  if(c == 1) ret.first++;
  else ret.second++;
  
  for(auto u : G[v]){
    if(u == p || color[u] == -c) continue;
    if(color[u] == c) return P(-1, -1);
    P res = dfs(u, v, -c);
    if(res.first == -1) return P(-1, -1);
    ret.first += res.first, ret.second += res.second;
  }
  return ret;
}

int main(void)
{
  cin >> n >> m;
  int u, v;
  for(int i = 1; i <= m; i++){
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  
  ll ans = n*(n-1)/2 - m;
  for(int i = 1; i <= n; i++){
    if(!color[i]){
      P res = dfs(i, -1, 1);
      if(res.first == -1){
        cout << 0 << endl;
        return 0;
      }
      ans -= res.first * (res.first-1) / 2;
      ans -= res.second * (res.second-1) / 2;
    }
  }
  cout << ans << endl;
  
  return 0;
}

https://atcoder.jp/contests/abc282/editorial/5397より

色分けは深さ優先探索のが良いのか
uが今いる頂点、pが前いた頂点、cが色(1か-1)、retが各色の個数で二部グラフでないなら(-1,-1)を返す

色関係なく$${N}$$個の頂点を結ぶ辺の最大数は$${\frac{N(N-1)}{2}}$$、そこからすでに引かれている$${M}$$本と、同じ色の頂点を結ぶ辺の数を引けば答えになるから全ての頂点に対して色が無いならそこを起点にして探索して色分け

なるほど