AtCoder Beginner Contest 330

OKU

結果

A - Counting Passes : AC(1:36)
B - Minimize Abs 1 : AC(23:51)
C - Minimize Abs 2 : AC(65:52)
D - Counting Ls : AC(72:08)(2ペナ)
E - Mex and Update : 提出無し

A - Counting Passes

$${N}$$人の人がある試験を受け、それぞれ$${A_{i}}$$点を取った
合格点が$${L}$$点であるとき何人が合格したか求める問題

自分の回答

int main(){
  int N, L;
  cin >> N >> L;
  int ans = 0;
  for(int i = 0; i < N; i++){
    int a;
    cin >> a;
    if(a >= L){
      ans++;
    }
  }

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

そのまま

公式解説

省略

B - Minimize Abs 1

長さ$${N}$$の整数列$${A}$$と整数$${L,R}$$が与えられる
$${L}$$以上$${R}$$以下であり、$${L}$$以上$${R}$$以下の整数$${Y}$$すべてにおいて$${|X-A_{i}|\leqq|Y-A_{i}|}$$となる整数$${X}$$を全ての$${A_{i}}$$において求める問題

自分の回答

int main(){
  int N, L, R;
  cin >> N >> L >> R;

  for(int i = 0; i < N; i++){
    int a;
    cin >> a;
    if(a < L){
      printf("%d ", L);
    }
    else if(a > R){
      printf("%d ", R);
    }
    else{
      printf("%d ", a);
    }
  }

  printf("\n");
}

だいぶ理解に時間がかかってしまったけど要は|X-A[i]|=min(|Y-A_[i]|)(Y=L;Y<=R)を求める問題でどの数になるかはA[i]がLRの範囲内ならA[i]、L未満ならL、Rより大きいならばRなためそう書いて終わり

公式解説

#define rep(i, x) for(int i = 0; i < (x); i++)

int main() {
    int n, l, r;
    cin >> n >> l >> r;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cout << clamp(a[i], l, r) << " \n"[i == n - 1];
}

https://atcoder.jp/contests/abc330/editorial/7748より

そうかmin(max(L,A[i]),R)でいいんだ

なるほど

C - Minimize Abs 2

正整数$${D}$$が与えられ、非負整数$${x,y}$$に対する$${|x^2+y^2-D|}$$の最小値を求める問題

自分の回答

int main(){
  int64_t D;
  cin >> D;

  int64_t ans = D;
  for(int64_t i = 0; i * i <= D; i++){
    int64_t sq = sqrt(abs(i * i - D));
    for(int j = -5; j < 5; j++){
      ans=min(ans,abs(i * i + (sq + j) * (sq + j) - D));
    }
  }

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

まずxyは入れ替えても問題ないためxだけを全て見る
そしてx^2がDを超えるとyが非負整数なためそれ以上は値が上昇する一方だからxは0から√D以下
そしてあるxにおいて式の値が0になるyは√|x^2-D|だがyは整数のため小数点以下切り捨てして前後をある程度調べる

公式解説

省略

D - Counting Ls

$${N×N}$$のマス目全てに「o」か「x」が書かれている
以下の条件を全て満たす$${3}$$マスの組がいくつあるか求める問題
・マスは全て相異なる
・マスは全て「o」である
・マスのうちちょうど$${2}$$つが同じ行にある
・マスのうちちょうど$${2}$$つが同じ列にある

自分の回答

int main(){
  int N;
  cin >> N;
  vector<vector<bool>> B(N, vector<bool>(N, false));
  vector<int> row(N, 0),line(N, 0);
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      char c;
      cin >>c ;
      if(c == 'o'){
        B[i][j] = true;
        line[i]++;
        row[j]++;
      }
    }
  }

  int64_t ans = 0;
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      if(B[i][j]){
        ans += (line[i] - 1) * (row[j] - 1);
      }
    }
  }

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

まず各行、列にoがいくつあるかを調べる
そうすればoのマスがあった時にそのマスをLの直角部とするものの数がそのマスの(行のoの数-1)×(列のoの数-1)で求められる

最初列はこの考えできたけど行もできることに気付かず行のペアを総当たりしてN^3でダメだよなとは思いながらも出してTLE
あと答えがintを超えることに気付かずWA

公式解説

省略

E - Mex and Update

長さ$${N}$$の数列$${A}$$が与えられる
$${A_{i_{k}}}$$を$${X_{k}}$$に変更した後、$${A}$$に含まれない最小の非負整数を出力するクエリが$${Q}$$個与えられるため全て処理する問題

自分の回答

int main(){
  int N, Q;
  cin >> N >> Q;
  set<int> mi;
  for(int i = 0; i <= N; i++){
    mi.insert(i);
  }
  map<int,int> ad;
  vector<int> A(N + 1);
  for(int i = 1; i <= N; i++){
    cin >> A[i];
    ad[A[i]]++;
    mi.erase(A[i]);
  }

  for(int _ = 0; _ < Q; _++){
    int i, x;
    cin >> i >> x;
    ad[A[i]]--;
    if(ad[A[i]] == 0){
      mi.insert(A[i]);
    }
    A[i] = x;
    mi.erase(x);
    ad[x]++;
    printf("%d\n", *begin(mi));
  }
}

今どの値がAに無いかを管理したいけど値は10^9まであるからそのままだと要素数的に無理、しかしAの要素数がNのため出力候補は0からNまでのN+1個とれば必ずその中にAに含まれない値が出てくるため、Nは最大2×10^5でコンテナで管理できる
そうしたら数列とどの値が何個あるかと数列に含まれていない値を管理すればok

1分足りなかった…

公式解説

int main(){
  int n,q;
  cin >> n >> q;
  vector<int> bk(n+1,0);
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin >> a[i];
    if(a[i]<=n){
      bk[a[i]]++;
    }
  }
  set<int> st;
  for(int i=0;i<=n;i++){
    if(bk[i]==0){st.insert(i);}
  }
  while(q>0){
    q--;
    int i,x;
    cin >> i >> x;
    i--;
    if(a[i]<=n){
      bk[a[i]]--;
      if(bk[a[i]]==0){st.insert(a[i]);}
    }
    a[i]=x;
    if(a[i]<=n){
      if(bk[a[i]]==0){st.erase(a[i]);}
      bk[a[i]]++;
    }
    cout << (*st.begin()) << "\n";
  }
  return 0;
}

https://atcoder.jp/contests/abc330/editorial/7752より

そうかそもそも値がNを超える場合は無視して問題ないんだ

なるほど

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