【競プロ精進ログ】ABC113-B

zuka

ABCをコツコツ解いていきます。

本記事は,管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために,積極的にアウトプットしていく作戦です。

これから競技プログラミングを始めようと考えている人や,なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。

目次

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest(通称ABC)を解いていくものです。今回はABC113-B「Palace」です。

ポイント

おさえておくべき内容がてんこ盛りのB問題でした。最初に注目するポイントとして,小数点の演算は誤差が発生しやすいため,できるだけ避けた方が無難だということが挙げられます。今回は,各地点における$A$度との差が問題でした。この差は必ずしも小数の世界で計算しなくてもOKです。

具体的には,標高が$x$メートルの地点の気温の$A$度との差$G$は以下のようにして求められます。

\begin{align}
G &= |(T – 0.006x) – A |
\end{align}

しかし,これでは$0.006x$の部分が小数になってしまうため,以下のように両辺を1000倍して考えます。

\begin{align}
1000G &= |(1000T – x) – 1000A |
\end{align}

$G$の大小と$1000G$の大小は一対一対応しますので,各地点で$1000G$の値を求めていけばOKです。


2つめのポイントは,各地点で$1000G$の値を求めた後に,最小となる地点のインデックスを求める作業です。いわゆるargminです。c++でargminを実現する主な方法には,以下の2つがあります。

argmin(argmax)の実現方法
  • ソートされていない配列に対してmin_elementを利用して最小要素インデックスのイテレータを取得後,先頭要素のイテレータとの距離を測る
  • ソートされている配列に対してlower_boundを利用して最小要素インデックスのイテレータを取得後,先頭要素のイテレータとの距離を測る

今回の配列はソートされていませんのでmin_elementを利用します。配列をソートして扱うと,地点の番号がぐちゃぐちゃになってしまいますからね。

おさえるべき内容

 小数の演算はなるべく避ける

 argminの実現方法

実装

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;


int main(){
  ll N, T, A;
  cin >> N >> T >> A;
  vector<ll> H(N);

  rep(i, N) cin >> H[i];

  // 1000Gを計算
  rep(i, N) H[i] = abs(T*1000 - H[i]*6 - A*1000);

  // Hがソートされていないときはmin_elementを利用できる
  auto index = min_element(H.begin(), H.end());
  // 先頭要素のインデックスとの距離を測る
  int ans = index - H.begin();
  // 0インデックスを1インデックスに直す
  cout << ans + 1 << endl;
}
よかったらシェアしてね!

コメント

コメントする

目次
閉じる