AtCoder Beginner Contest 293

AtCoder Beginner Contest 293 - AtCoder

結果

A - Swap Odd and Even:AC(2:51)
B - Call the ID Number:AC(10:13)
C - Make Takahashi Happy:AC(31:14)
D - Tying Rope:AC(56:45)
E - Geometric Progression:提出無し

A - Swap Odd and Even

英小文字からなる文字列$${S}$$が与えられ、奇数文字目の文字とその次の文字を入れ替えた文字列を出力する問題

自分の回答

int main(){
  string S;
  cin >> S;

  for(int i = 0; i < S.size(); i += 2){
    swap(S[i], S[i + 1]);
  }

  printf("%s\n",S.c_str());
}

そのまま

公式解説

省略

B - Call the ID Number

$${1}$$から$${N}$$までの番号が付けられた人が存在し、$${1}$$から$${N}$$まで順番に自身が呼ばれていないならば$${A_{i}}$$番の人を呼ぶ操作をする
全ての操作が終わった時、呼ばれていない人の番号を昇順に出力する問題

自分の回答

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }

  vector<bool> C(N, false);
  for(int i = 0; i < N; i++){
    if(C[i]){
      continue;
    }
    C[A[i] - 1]=true;
  }

  int ans = 0;
  vector<int> Cans;
  for(int i = 0; i < N; i++){
    if(C[i] == false){
      ans++;
      Cans.push_back(i + 1);
    }
  }

  printf("%d\n", ans);
  for(int i = 0; i < ans; i++){
    printf("%d",Cans[i]);
    printf(i != ans - 1 ? " " : "\n");
  }
}

呼ばれたかを管理するboolの配列を作って操作の通りに
だけどAはいらなかったな

公式解説

省略

C - Make Takahashi Happy

$${H}$$行$${W}$$列のマス目があり、各マスには整数が書かれている
高橋君は$${(1,1)}$$から右もしくは下のマスに移動する操作を繰り返して$${(H,W)}$$まで行く
この時通ったマスに書かれていた数字が全て異なる移動経路はいくつあるか求める問題

自分の回答

set<int> C;
vector<vector<int>> A(12, vector<int>(12, 0));
int ans = 0;

void dfs(int nowi, int nowj, int H, int W){
  if(nowi == H && nowj == W){
    ans++;
    return;
  }

  C.insert(A[nowi][nowj]);
  if(!C.count(A[nowi][nowj + 1])){
    dfs(nowi, nowj + 1, H, W);
  }
  if(!C.count(A[nowi + 1][nowj])){
    dfs(nowi + 1, nowj, H, W);
  }

  C.erase(A[nowi][nowj]);
  return;
}
 
int main(){
  int H, W;
  cin >> H >> W;
  for(int i = 1; i <= H; i++){
    for(int j = 1; j <= W; j++){
      cin >> A[i][j];
    }
  }

  C.insert(0);
  C.insert(A[1][1]);
  dfs(1, 1, H, W);

  printf("%d\n",ans);
}

H,W共に最大10だったためsetにこれまで通ったマスの数字を入れて深さ優先探索で総当たり
マス目に存在しない0をマスの外に配置して端にいる時の特殊処理がいらなくなる

公式解説

int main(void)
{
  int h, w;
  int a[11][11];
  
  cin >> h >> w;
  for(int y = 1; y <= h; y++) for(int x = 1; x <= w; x++) cin >> a[x][y];
  
  int p[20], l = h+w-2, ans = 0;
  for(int i = 1; i <= l; i++){
    if(i > w-1) p[i] = 1;
    else p[i] = 0;
  }
  
  do{
    int x = 1, y = 1;
    set<int> S; S.insert(a[1][1]);
    for(int i = 1; i <= l; i++){
      if(p[i]) y++;
      else x++;
      S.insert(a[x][y]);
    }
    if(S.size() == l+1) ans++;
  }while(next_permutation(p+1, p+l+1));
  
  cout << ans << endl;
  return 0;
}

https://atcoder.jp/contests/abc293/editorial/5948より

右への移動と下への移動を01で表してそれをnext_permutationで回して総当たりか

なるほど

D - Tying Rope

一端が赤に、もう一端が青に塗られたロープが$${N}$$本あり、ロープ$${A_{i}}$$の色$${B_{i}}$$とロープ$${C_{i}}$$の色$${D_{i}}$$を結ぶ操作を$${M}$$回行う、この時各ロープの同じ色が複数回結ばれることはない
全ての操作を行った後、ひとつながりになっているロープ全てにおいて環状になっているものの数となっていないものの数を求める問題

自分の回答

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

  dsu G(N);
  int a, c, cyc = 0;
  char b, d;
  for(int i = 0; i < M; i++){
    cin >> a >> b >> c >> d;
    a--;
    c--;
    if(G.leader(a) == G.leader(c)){
      cyc++;
    }
    G.merge(a, c);
  }

  printf("%d %d\n",cyc, G.groups().size() - cyc);
}

要は各頂点に繋がる辺の数が2本までに制限されているグラフで連結成分がいくつあるかとその中に閉路がいくつあるかを求める問題で、閉路はすでに同じ木に属する頂点が結ばれたときにできるためACLで入力ごとに調べて繋げてを繰り返していく

公式解説

省略

E - Geometric Progression

整数$${A,X,M}$$が与えられ、$${\displaystyle\sum_{i=0}^{X-1}A^i}$$を$${M}$$で割った余りを求める問題

自分の回答

計算量をXまではできたけどそれじゃあ足りない…
それ以上は思いつかなかった

公式解説

$${A^0+A^1+A^2+…+A^n}$$を真ん中で分けると右=左×右の先頭になるからそれを再帰していけばlogXで解ける…ってことでいいのかな…

理解しきれんかった…