AtCoder Beginner Contest 112

AtCoder Beginner Contest 112 - AtCoder

A - Programming Education

問題

A - Programming Education

考察

の値が1の場合は文字列を出力し、2の場合は計算をする問題。の値に応じて処理するだけ。

コード

int main(){
  int n;
  cin >> n;
  if(n==1){
    cout << "Hello World"<< endl;
  }else{
    int a,b;
    cin >> a >> b;
    cout << a+b << endl;
  }
  return 0;
}

B - Time Limit Exceeded

問題

B - Time Limit Exceeded

考察

制限時間に対し、個のコストと時間をもつ経路があり、制限時間内である経路のうち最小のコストを求める。ループで個すべての経路に対して制限時間内かどうかを判定し、最小コストを更新していけばよい。

コード

int main(){
  ll n,t;
  cin >> n >> t;
  ll cost_min = INF;
  REP(i,n){
    ll c,t1;
    cin >> c >> t1;
    if(t1<=t&&c<cost_min){
      cost_min = c;
    }
  }
  if(cost_min==INF){
    cout << "TLE" << endl;
  }else{
    cout << cost_min << endl;
  }
  return 0;
}

C - Pyramid

問題

C - Pyramid

考察

平面上の各点に高さが与えられていて、ある点を中心としたピラミッドのようになっているとき、点の座標における高さからピラミッドの中心と高さを求める問題。
ピラミッドの中心は100×100マスの中のいずれかなので、ここで全探索が可能である。各点の高さは0以上に変換されてしまうことに注意して、点のうち最も高さが高い点の座標と高さを保持しておき、その点を基準としてピラミッドの高さを計算する。あとは他の点が矛盾ないかどうかをチェックしていけばよい。

コード

int main(){
  int n;
  cin >> n;
  int x[n], y[n];
  ll h[n];
  ll max_h = 0, max_x, max_y;
  REP(i,n){
    cin >> x[i] >> y[i] >> h[i];
    if(h[i]>=max_h){
      max_h = h[i];
      max_x = x[i], max_y = y[i];
    }
  }
  for(int cx = 0; cx <=100; cx++){
    for(int cy = 0; cy <=100; cy++){
      ll ch = max_h + abs(max_x-cx) + abs(max_y-cy);
      REP(i,n){
        if(h[i]!=max((ll)0,ch-abs(x[i]-cx)-abs(y[i]-cy))){
          goto next;
        }
      }
      cout << cx << " "<< cy <<" " << ch << endl;
      return 0;
      next:;
    }
  }
  return 0;
}

D - Partition

問題

D - Partition

考察

自然数が与えられ、個の自然数の和がとなるようにするとき、の最大公約数の最大値を求める。
最大公約数を、をで定めるとき、はと書き換えられる。左辺は以上なので、は以下である必要があり、逆にこれが満たされればを定めることができる。よって求めるべきは以下の最大のの約数で、以下で探索できる。

コード

int main(){
  ll n,m;
  cin >> n >> m;
  ll i_max = 1;
  for(ll i = 1; i*i<=m; i++){
    if(m%i==0){
      if(i<=m/n){
        i_max = max(i,i_max);
      }
      if(m/i<=m/n){
        i_max = max(m/i,i_max);
      }
    }
  }
  cout << i_max << endl;
  return 0;
}

雑感

ひさびさに参加。Cは落ち着いて考えたら行けた。逆にDで取り返そうとして焦ったらTLEとWAを量産してしまい、Dで3ペナルティ。longのところをintと書いた自分を殴りたい。