AtCoder Beginner Contest 273

OKU

結果

A - A Recursive Function:AC(3:13)
B - Broken Rounding:AC(38:44)
C - (K+1)-th Largest Number:AC(94:37)(1ペナ)
D - LRUD Instructions:提出無し

A - A Recursive Function

非負整数$${N}$$が与えられ
$${f(0)=1}$$、任意の正整数kに対し$${f(k)=k×f(k-1)}$$である関数$${f(N)}$$の値を求める問題

自分の回答

int main(){
  int N;
  cin >> N;
 
  if(N == 0){
    printf("1\n");
  }
  else{
    int ans = 1;
    for(int i = 1; i <= N; i++){
      ans *= i;
    }
    printf("%d\n",ans);
  }
}

要は0の時を除けば階乗なためforで計算
再帰関数でやれば0を分離しないでも行けたな

公式解説

int f(int x){
  if(x==0){return 1;}
  return x*f(x-1);
}

int main(){
  int n;
  cin >> n;
  cout << f(n) << "\n";
  return 0;
}

https://atcoder.jp/contests/abc273/editorial/5017より

やっぱりそうよね

B - Broken Rounding

非負整数$${X}$$が与えられ、1から$${K-1}$$の位まで順番に四捨五入をしていった値を求める
厳密には$${X}$$を「$${|Y-X|}$$が最小となる$${10^{i+1}}$$の倍数のうち最小のもの」である$${Y}$$に置き換える操作をする

自分の回答

int main(){
  int64_t X, K;
  cin >> X >> K;
 
  int64_t D = 1;
  for(int i = 0; i < K; i++){
    D *= 10;
    int64_t Y1 = X / D * D;
    int64_t Y2 = X / D * D + D;
    abs(Y1 - X) < abs(Y2 - X) ? X = Y1 : X = Y2;
  }

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

最初は10%Dが5以上になるときDを足してX/D*Dと四捨五入を書いてみたけど15 2みたいなときに100となってしまい、原因がわからず厳密な操作の方で書いた

公式解説

int main(){
  long long x,k;
  cin >> x >> k;
  long long pow10=1;
  for(long long i=0;i<k;i++){
    x/=pow10;
    long long m=(x%10);
    if(m<=4){x-=m;}
    else{x+=(10-m);}
    x*=pow10;
    pow10*=10;
  }
  cout << x << "\n";
  return 0;
}

https://atcoder.jp/contests/abc273/editorial/5033より

$${i}$$桁目を操作したいときはまず$${10^{i-1}}$$で割れば後の操作を統一できるのか
そして10で割った余りmが4以下ならXからmを引いて、そうでないならXに10足してm引けばいいのか

なるほど

C - (K+1)-th Largest Number

長さ$${N}$$の整数列$${A=(A_{1},A_{2},…A_{N})}$$が与えられ、$${A}$$に含まれる値のうち$${A_{i}}$$より大きいものが何種類あるかを0から$${N-1}$$まで求める問題

自分の回答

int main(){
  int N;
  cin >> N;
  vector<int> seq;
  map<int, int> number;
  for(int i = 0; i < N; i++){
    int a;
    cin >> a;
    if(number.count(a)){
      number[a]++;
    }
    else{
      number[a] = 1;
      seq.push_back(a);
    }
  }

  sort(seq.begin(), seq.end(), greater<int>());
  int Size = seq.size();
 
  for(int i = 0; i < N; i++){
    if(i < seq.size()){
      printf("%d\n",number[seq[i]]);
    }
    else{
      printf("0\n");
    }
  }
}

最初は愚直に調べる方法で(多少の計算量削減はしたけど)TLE
そこで考えてる内にわざわざ値を比較しなくても答えは求められるのでは？と思いできたのがこれ
試行錯誤の残骸が残ってる
seqが$${A}$$から重複を除いたもの
numberで各値が何個あったかを管理
$${A_{i}}$$より大きい値が0種類=$${A_{i}}$$は$${A}$$の中で最大
1種類=2番目に大きい
2種類=3番目に大きい
……
となるためseqを降順でソートして先頭からその値がいくつ出てきたかを出力すれば求められる出力となる

公式解説

int main(void)
{
  int n, a;
  map<int, int> mp;
  
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a, mp[a]++;
  for(auto it = mp.rbegin(); it != mp.rend(); it++) cout << it->second << "\n";
  for(int i = 1; i <= n - (int)mp.size(); i++) cout << 0 << "\n";
  
  return 0;
}

https://atcoder.jp/contests/abc273/editorial/5018より

そうかsetはそもそもソートされてるからケツから見て行けばそれでいいのか

なるほど

D - LRUD Instructions

$${H}$$行$${W}$$列のグリッドの中に$${N}$$個の壁があり
L(左),R(右),U(上),D(下)に$${l_{i}}$$マス移動する指示が$${Q}$$個与えられ、最初$${(r_{s},r_{s})}$$にいるとき指示を全て終わらせたらどのマスにいるかを求める問題
ただし移動は壁にぶつかるとそこで止まり、次の指示を実行する

自分の回答

C問題を解けたのが時間ぎりぎりだったから問題を読んだ程度だったけど

現在地から壁が無かった時の移動先を求めて始点と終点の間に壁があるかを判定、あったならその手前のマスを現在地とする
の繰り返しで行けるかな…

公式解説

int h, w, n, r, c, Q;
map<int, vector<int>> amp, bmp;

int main(void)
{
  cin >> h >> w >> r >> c >> n;
  for(int i = 1; i <= n; i++){
    int rr, cc;
    cin >> rr >> cc;
    amp[rr].push_back(cc), bmp[cc].push_back(rr);
  }
  for(auto &p : amp) sort(p.second.begin(), p.second.end());
  for(auto &p : bmp) sort(p.second.begin(), p.second.end());
  
  cin >> Q;
  char d; int l;
  for(int i = 1; i <= Q; i++){
    cin >> d >> l;
    if(d == 'L'){
      auto it = amp.find(r); int lb = 0;
      if(it != amp.end()){
        vector<int> &vec = it->second;
        auto it2 = lower_bound(vec.begin(), vec.end(), c);
        if(it2 != vec.begin()) it2--, lb = *it2;
      }
      c = max(c-l, lb+1);
    }
    if(d == 'U'){
      auto it = bmp.find(c); int lb = 0;
      if(it != bmp.end()){
        vector<int> &vec = it->second;
        auto it2 = lower_bound(vec.begin(), vec.end(), r);
        if(it2 != vec.begin()) it2--, lb = *it2;
      }
      r = max(r-l, lb+1);
    }
    if(d == 'R'){
      auto it = amp.find(r); int ub = w+1;
      if(it != amp.end()){
        vector<int> &vec = it->second;
        auto it2 = upper_bound(vec.begin(), vec.end(), c);
        if(it2 != vec.end()) ub = *it2;
      }
      c = min(c+l, ub-1);
    }
    if(d == 'D'){
      auto it = bmp.find(c); int ub = h+1;
      if(it != bmp.end()){
        vector<int> &vec = it->second;
        auto it2 = upper_bound(vec.begin(), vec.end(), r);
        if(it2 != vec.end()) ub = *it2;
      }
      r = min(r+l, ub-1);
    }
    cout << r << " " << c << "\n";
  }
  
  return 0;
}

https://atcoder.jp/contests/abc273/editorial/5022より

基本的な考え方は合ってるっぽいかな
ただ壁の位置をmapで縦横分けるのか
たしかにそっちの方がいろいろやりやすいな

なるほど

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