AtCoder Beginner Contest 294

2023年3月20日 16:25

結果

A - Filter : AC(5:00)
B - ASCII Art : AC(7:38)
C - Merge Sequences : AC(17:53)
D - Bank : AC(30:38)
E - 2xN Grid : AC(63:28)
F - Sugar Water 2 : 提出無し

A - Filter

長さ$${N}$$の整数列$${A=(A_{1},A_{2},…,A_{N})}$$が与えられ、その中から偶数のみを順番を変えずに出力する問題

自分の回答

int main(){
  int N, a;
  cin >> N;
  queue<int> ans;
  for(int i = 0; i < N; i++){
    cin >> a;
    if(a % 2 == 0){
      ans.push(a);
    }
  }

  printf("%d", ans.front());
  ans.pop();
  while(!ans.empty()){
    printf(" %d", ans.front());
    ans.pop();
  }
  printf("\n");
}

そのままだけどなんか妙にめんどくさくなった

公式解説

省略

B - ASCII Art

$${0}$$以上$${26}$$以下の整数からなる$${H}$$行$${W}$$列の行列$${A}$$が与えられ、$${A_{i,j}}$$が$${0}$$なら「.」を、そうでないならば大文字アルファベットの$${A_{i,j}}$$文字目にして出力する問題

自分の回答

int main(){
  int H, W;
  cin >> H >> W;

  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      int a;
      cin >> a;
      printf(a == 0 ? "." : "%c", 64 + a);
    }
    printf("\n");
  }
}

そのまま

公式解説

省略

C - Merge Sequences

長さ$${N}$$の狭義単調増加列$${A=(A_{1},A_{2},…,A_{N})}$$と長さ$${M}$$の狭義単調増加列$${B=(B_{1},B_{2},…,B_{N})}$$が与えられ、$${A,B}$$をまとめて昇順にソートしたものを$${C}$$とする
$${A,B}$$それぞれの要素が$${C}$$において何番目に存在するかを求める問題

自分の回答

int main(){
  int N, M;
  cin >> N >> M;
  vector<pair<int, char>> C;
  int s;
  for(int i = 0; i < N; i++){
    cin >> s;
    C.push_back({s, 'A'});
  }
  for(int i = 0; i < M; i++){
    cin >> s;
    C.push_back({s, 'B'});
  }

  sort(C.begin(), C.end());
  vector<int> ansa, ansb;
  int i = 1;
  for(auto [n, c] : C){
    if(c == 'A'){
      ansa.push_back(i);
    }
    else{
      ansb.push_back(i);
    }
    i++;
  }

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

Cを作って先頭からどっちにあるかを毎回調べて行ったら時間足りるか怪しかったから数字とどっちにあったかのpairにしてそれを基に分類

公式解説

int main() {
    using namespace std;

    unsigned N, M;
    cin >> N >> M;

    vector<pair<unsigned, unsigned>> A(N), B(M);
    for (auto&&[a, _] : A) cin >> a;
    for (auto&&[b, _] : B) cin >> b;
    for (unsigned i{}; i < N; ++i) A[i].second = i;
    for (unsigned i{}; i < M; ++i) B[i].second = i + N;

    vector<pair<unsigned, unsigned>> C(N + M);
    merge(begin(A), end(A), begin(B), end(B), begin(C));

    vector<unsigned> ans(N + M);
    for (unsigned i{}; i < N + M; ++i) ans[C[i].second] = i;

    for (unsigned i{}; i < N + M; ++i) cout << ans[i] + 1 << " ";

    return 0;
}

https://atcoder.jp/contests/abc294/editorial/5989より

A,Bは最初からソートされてるからmergeを使うとN+Mでできるのか

なるほど

D - Bank

銀行に人$${1}$$~人$${N}$$が並んでいて、$${Q}$$個のイベントが発生する、イベントは以下の3種類のいずれか
・1 : 受付に呼ばれていない人の内、最も小さい番号の人が呼ばれる
・2 x : 人$${x}$$が受付に行く(人$${x}$$は$${1}$$回以上呼ばれている)
・3 : 受付に呼ばれているが来ていない人の内、最も小さい番号を呼ぶ
イベント3においてどの番号が呼ばれるかを出力する問題

自分の回答

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

  set<int> done;
  int call = 1;
  for(int i = 0; i < Q; i++){
    int t;
    cin >> t;
    if(t == 2){
      int  c;
      cin >> c;
      done.insert(c);
    }
    else if(t == 3){
      while(done.count(call)){
        call++;
      }
      printf("%d\n", call);
    }
  }
}

どの人が来たかをsetに入れてイベント3が来たら3で呼んでないうち最小の番号であるcallを来てない番号になるまでインクリメント
制約からイベント1は無視してかまわない

公式解説

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, Q;
  cin >> N >> Q;
  vector<int> gone(N + 1);
  int ans = 1;
  while (Q--) {
    int event;
    cin >> event;
    if (event == 1) {
      // do nothing
    } else if (event == 2) {
      int x;
      cin >> x;
      gone[x] = 1;
    } else {
      while (gone[ans]) ans++;
      cout << ans << "\n";
    }
  }
}

https://atcoder.jp/contests/abc294/editorial/6005より

要素数500000のvectorは問題ないのか
駄目かと思ってsetにしたけど大丈夫ならこっちのが早いよな

E - 2xN Grid

$${2}$$行$${L}$$列のマス目があり、各マスには整数が書かれている
同じ列にある数字が等しい列がいくつあるかを求める問題
ただし入力は連長圧縮(aがb個連続してあるという形)でされる

自分の回答

int main(){
  int64_t L;
  int N1, N2;
  cin >> L >> N1 >> N2;
  queue<pair<int,int64_t>> X1, X2;
  int v;
  int64_t l;
  for(int i = 0; i < N1; i++){
    cin >> v >> l;
    X1.push({v, l});
  }
  for(int i = 0; i < N2; i++){
    cin >> v >> l;
    X2.push({v, l});
  }

  int64_t ans = 0;
  while(!X1.empty()){
    if(X1.front().first == X2.front().first){
      ans += min(X1.front().second, X2.front().second);
    }

    if(X1.front().second == X2.front().second){
      X1.pop();
      X2.pop();
    }
    else if(X1.front().second < X2.front().second){
      X2.front().second -= X1.front().second;
      X1.pop();
    }
    else{
      X1.front().second -= X2.front().second;
      X2.pop();
    }
  }

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

計算量がLだと駄目そうだったからX1,X2のsecond(いくつあるか)を比べて減らしてを繰り返して行ったら足りた

公式解説

何やってるのかわからん…

F - Sugar Water 2

高橋君が$${N}$$本の、青木君が$${M}$$本の砂糖水を持っている、二人の持っている砂糖水を1本づつ選んで混ぜた時$${K}$$番目に濃度が高い砂糖水は濃度何%かを求める問題

自分の回答

どう計算量を削減するかさっぱりわからなかった

公式解説

int main() {
  long long N, M, K;
  cin >> N >> M >> K;
  vector<long long> A(N), B(N), C(M), D(M);
  for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
  for (int i = 0; i < M; i++) cin >> C[i] >> D[i];
  double ng = 0, ok = 1;
  for (int iter = 0; iter < 100; iter++) {
    double x = (ng + ok) / 2;
    double z = x / (1 - x);
    vector<double> v(M);
    for (int i = 0; i < M; i++) v[i] = C[i] - D[i] * z;
    sort(begin(v), end(v));
    long long num = 0;
    for (int i = 0; i < N; i++) {
      double w = A[i] - B[i] * z;
      num += M - (lower_bound(begin(v), end(v), -w) - begin(v));
    }
    (num < K ? ok : ng) = x;
  }
  cout << fixed << setprecision(16) << ok * 100 << "\n";
}

https://atcoder.jp/contests/abc294/editorial/6007より

濃度を決めてそれ以上になるためにはどれだけ砂糖が必要かを求めて、それをソートすれば二分探索ができるからそれで濃度以上になるのが何通りあるかを求めて、それを基に濃度を調節してを繰り返していく…でいいのかな…

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