AtCoder Beginner Contest 289

OKU

結果

A - flip:AC(1:44)
B - レ:AC(28:48)
C - Coverage:AC(58:24)
D - Step Up Robot:AC(87:44)(3ペナ)
E - Swap Places:提出無し

A - flip

0と1からなる文字列$${s}$$が与えられ、0を1に、1を0にした文字列を出力する問題

自分の回答

int main(){
  string S;
  cin >> S;
  for(char c : S){
    printf(c == '0' ? "1" : "0" );
  }
  printf("\n");
}

そのまま

公式解説

省略

B - レ

古文におけるレ点が何文字目の後ろにあるかが入力されるため読み順を求める問題

自分の回答

int main(){
  int N, M;
  cin >> N >> M;
  vector<bool> G(N + 1);
  int a;
  for(int i = 0; i < M; i++){
    cin >> a;
    G[a] = true;
  }

  vector<int> ans;
  queue<int> bfs;
  vector<bool> check(N + 1, false);
  for(int i = 1; i <= N; i++){
    if(check[i]){
      continue;
    }
    bfs.push(i);
    check[i] = true;
    stack<int> re;
    re.push(i);
    while(!bfs.empty()){
      int now = bfs.front();
      bfs.pop();
      if(G[now]){
        bfs.push(now + 1);
        check[now + 1] = true;
        re.push(now + 1);
      }
    }
    while(!re.empty()){
      ans.push_back(re.top());
      re.pop();
    }
  }
  for(int i = 0; i < N; i++){
    printf("%d", ans[i]);
    printf(i != N - 1 ? " " : "\n");
  }
}

いろいろ試したけどうまくいかなかったから問題文にあるグラフ解釈で幅優先探索して書いた
深さ優先探索の方が良かったかな

間違いなくB問題で要求されるコードではない
出力の文字区切りがスペースじゃなければもっと簡単に書けたんだけど…

公式解説

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> a(M);
  for (auto& x : a) cin >> x;
  vector<int> re(N + 1);
  for (auto& x : a) re[x] = 1;
  vector<int> ans;
  for (int i = 1, j = 1; i <= N; i = ++j) {
    while (re[j]) j++;
    for (int k = j; k >= i; k--) ans.push_back(k);
  }
  for (int i = 0; i < N; i++) cout << ans[i] << " \n"[i + 1 == N];
}

https://atcoder.jp/contests/abc289/editorial/5731より

レ点がある限りjをインクリメントしていって無くなったらiまでansに入れながらデクリメントか

なるほど

C - Coverage

$${1}$$以上$${N}$$以下の整数からなる集合が$${M}$$個ある
この中から1つ以上の集合を選んだ時$${1}$$から$${N}$$まで全ての要素が少なくとも1つ存在する組み合わせは何通りあるかを求める問題

自分の回答

int main(){
  int N, M;
  cin >> N >> M;
  vector<bitset<11>> C(M);
  for(int i = 0; i < M; i++){
    int c;
    cin >> c;
    for(int j = 0; j < c; j++){
      int a;
      cin >> a;
      C[i].set(a);
    }
  }

  int ans = 0;
  for(int tmp = 0; tmp < (1 << M); tmp++){
    bitset<11> s;
    for(int i = 0; i < M; i++){
      if(tmp & (1 << i)){
        s |= C[i];
      }
    }
    bool all = true;
    for(int i = 1; i <= N; i++){
      if(s.test(i) == false){
        all = false;
      }
    }
    if(all){
      ans++;
    }
  }

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

NもMも最大10なためbit全探索で総当たり

公式解説

省略

D - Step Up Robot

階段の0段目にロボットが存在し、このロボットは1回の動作で$${A_{1},A_{2},…,A_{N}}$$段の階段を上ることができる
また、階段の$${B_{1},B_{2},…,B_{M}}$$段目にはモチがあり、その段に行くとそれ以上動けなくなる
この時ロボットは$${X}$$段目に到達できるか判定する問題

自分の回答

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }
  int M;
  cin >> M;
  vector<int> st(100001, 0);
  st[0] = 1;
  int b;
  for(int i = 0; i < M; i++){
    cin >> b;
    st[b] = -1;
  }
  int X;
  cin >> X;

  for(int i = 0; i < X; i++){
    if(st[i] == 1){
      for(int x : A){
        int next = i + x;
        if(next > X){
          continue;
        }
        if(st[next] == -1){
          continue;
        }
        st[next] = 1;
      }
    }
  }

  printf(st[X] == 1 ? "Yes\n" : "No\n");
}

動的計画法でモチの情報(-1)を入れてそこを踏んだらスキップ

stの桁が1つ少なくて3回RE
WAじゃなかった時点で気付け…

公式解説

省略

E - Swap Places

$${N}$$頂点$${M}$$辺の単純無向グラフが与えられ、全ての頂点は赤か青に塗られている
・高橋君と青木君が今いる頂点と隣接する頂点のいずれかに同時に移動する、ただし2人の移動先の色はそれぞれ異なっている必要がある
最初高橋君が頂点1、青木君が頂点$${N}$$にいるとき、この行動を繰り返すことで高橋君が頂点$${N}$$、青木君が頂点1にいる状態にすることができるか、また、可能ならば最小何回で移動できるかを求める問題

自分の回答

探索して何回で目的地に移動できるかをそれぞれ求めるのかなと思ったけど同じ頂点を複数回通れるからその場合の管理方法とかを知らない…

公式解説

他の人の提出とかを漁ったりもしたけどグラフの到達済みのチェックを2人がどの頂点にいるかの組み合わせで管理して幅優先探索する感じかな
理解しきれてない…

この記事が気に入ったらサポートをしてみませんか？