abc253に挑んだ初心者の感想

abc253のa問題からd問題までの簡単な解説を載せます．

A - Median?

bが中央値かどうかを調べる問題です．a≦b≦cまたはc≦b≦aが成立すればOKなので以下のようになります．

int a, b, c;

int main(){
  cin >> a >> b >> c;

  if((a <= b && b <= c) || (c <= b && b <= a)) cout << "Yes" << endl;
  else cout << "No" << endl;
}

B - Distance Between Tokens

2つのoのマンハッタン距離を求めます．マンハッタン距離とは格子状の道路を移動する際の距離です．2点(x1, y1)、(x2, y2)間のマンハッタン距離は
                                     d = |x1 - x2| + |y1 - y2| 
となります．

vector<string> field(110);
int h, w;

int main(){
  cin >> h >> w;
  rep(i, 0, h){
    cin >> field.at(i);
  }

  vector<P> p;
  rep(i, 0, h){
    rep(j, 0, w){
      if(field.at(i).at(j)=='o') p.push_back(make_pair(i, j));
    }
  }

  cout << abs(p.at(0).first - p.at(1).first) + abs(p.at(0).second - p.at(1).second) << endl;
}

C. Max - Min Query

多重集合を扱います．mapを用いて、整数keyがvalue個あるとして考えました．mapの計算量は追加、参照、削除、最大値探索、最小値探索が全てmapの要素数の対数なので、操作1、2、3は全てO(logQ)で抑えられます．ちなみに、mapのkeyの最大値はm.rbegin()->first、最小値はm.begin()->firstで求められます．

)int q;
map<int, int> m;

int main(){
  cin >> q;
  rep(i, 0, q){
    int n, x, c;
    cin >> n;
    
    if(n == 1){
      cin >> x;
      if(m.find(x) == m.end()) m[x] = 1;
      else m[x]++;
    }
    else if(n == 2){
      cin >> x >> c;
      if(m.find(x) != m.end()){
        if(m[x] > c) m[x] -= c;
        else m.erase(x);
      }
    }
    else{
      cout << m.rbegin()->first - m.begin()->first << endl;
    }
  }
}

公式の解説ではmultisetという出来合いの多重集合を用いています．多分こちらを用いた方が良いです．

D - FizzBuzz Sum Hard

集合の問題です．全体の総和から、Aの倍数の総和とBの倍数の総和を引き、Aの倍数かつBの倍数の総和(AとBの最小公倍数の総和)を足せばよいと考えました．以下のようにベン図を書けばわかりやすいです．

ll n, a, b;

ll sigma(ll n){
  return n * (n+1) / 2;
}

int main(){
  cin >> n >> a >> b;

  ll res = 0;
  if(a != b) res = sigma(n) - a * sigma(n/a) - b * sigma(n/b) + lcm(a,b) * sigma(n/lcm(a, b));
  else res = sigma(n) - a * sigma(n/a);
  cout << res << endl;
}

さらに、A==Bの場合は条件が変わるので気を付けましょう．