AtCoderログ：0027 - ABC 113 B

問題：ABC 113 B - Palace

問題文

ある国で、宮殿を作ることになりました。
この国では、標高が $x$ メートルの地点での平均気温は $T−x \times 0.006$ 度です。
宮殿を建設する地点の候補は $N$ 個あり、地点 $i$ の標高は $H_i$ メートルです。
joisinoお姫様は、これらの中から平均気温が $A$ 度に最も近い地点を選んで宮殿を建設するようにあなたに命じました。
宮殿を建設すべき地点の番号を出力してください。
ただし、解は一意に定まることが保証されます。

制約

・$1 \le N \le 1000$
・$0 \le T \le 50$
・$-60 \le A \le T$
・$0 \le H_i \le 10^5$
・入力は全て整数
・解は一意に定まる

収録されている問題セット

• AtCoder に登録したら次にやること (第03問類題)

回答1 (AC)

各地点の標高に対して平均気温を計算し、平均気温と a との差の絶対値の最小値を求めれば良いです。コードは以下のようになりました。

abc113b-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, t, a;
  cin >> n;
  cin >> t >> a;
 
  int h, answer;
  float tempature, dmin = FLT_MAX;
  for ( int i=0; i<n; i++ ) {
    cin >> h;
    tempature = t-0.006*h;
    if ( abs(a-tempature)<dmin ) {
      dmin = abs(a-tempature);
      answer = i;
    }
  }
 
  cout << answer+1 << endl;
}

回答2 (AC)

回答1では各地点の標高から平均気温を計算しているため、$N$ 回の計算が必要になります。目標とする平均気温は $a$ なので、この平均気温になる標高を求め、この標高との差が最小となるような地点を求めることで、計算回数を 1 回に削減することができます。コードは以下のようになりました。

abc113b-2.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, t, a;
  cin >> n;
  cin >> t >> a;
  float x = (t-a)/0.006;

  int h, answer;
  float dmin = FLT_MAX;
  for ( int i=0; i<n; i++ ) {
    cin >> h;
    if ( abs(x-h)<dmin ) {
      dmin = abs(x-h);
      answer = i;
    }
  }

  cout << answer+1 << endl;
}

このコードを実行させたところ、実行時間もメモリも回答1とほとんど変わりませんでした。それくらい標高から平均気温を求める計算は軽い計算だったということでしょう。

調べたこと

AtCoder の解説 → ユーザ解説

回答1と同じ方針でした。浮動小数を使う場合には float 形よりも double 型が良いとのことです。

AtCoder の解説 → コンテスト全体の解説

回答1と同じ方針でしたが、「気温は整数ではありませんが、気温を 1000 倍して計算すると浮動小数点型を用いなくても答えを求めることができます」は参考になる工夫だと思いました。

リンク

• 前の記事 → AtCoderログ：0026 - ちょっとした方針変更
• 次の記事 → AtCoderログ：0028 - ARC 123 に参加しました