AtCoder ABC205 A~D問題をわかりやすく解説

AtCoder ABC205 A~D問題をわかりやすく解説します。

A – kcal

問題はこちら

解説

100mL当たり\(A\,\)kcalなので、1mLあたりは\(A / 100\,\)kcal。\(B\,\)mLでは\(A / 100 \times B\,\)となります。出力が誤差\(10^{-6}\)以下という制限があるので、double型で計算します。

ソースコード

#include <bits/stdc++.h>

int main() {
  double a, b; std::cin >> a >> b;
  double ans = a / 100 * b;
  std::cout << ans << std::endl;
  return 0;
}

B – Permutation Check

問題はこちら

解説

\(1\)から\(N\)までのすべての整数が存在するかチェックして、すべて存在すればYes、そうでなければNoを出力します。ソースコードでは\(-1\)して、\(0\)から\((N-1)\)までのすべての整数が存在するかどうかをチェックしています。

ソースコード

#include <bits/stdc++.h>

int main() {
  int n; std::cin >> n;
  std::vector<bool> a(n, false);
  for (int i = 0; i < n; ++i) {
    int num; std::cin >> num;
    a[--num] = true;
  }

  bool sortable = true;
  for (int i = 0; i < n; ++i)
    if (!a[i]) sortable = false;
  
  if (sortable) 
    std::cout << "Yes" << std::endl;
  else
    std::cout << "No" << std::endl;

  return 0;
  
}

C – POW

問題はこちら

解説

制約が\(-10^{-9} \leq A, B \leq 10^9\)、\(1 \leq C \leq 10^9 \)で、例えば\( A \)が\(10^9\)、\( C \)が\( 10^9 \)の時にはpow(\(A\), \(C)\)はlong longに収まりまらないので、愚直に計算して大小関係を割り出すのは無理です。

この場合\(C\)が共通しているので、\( A \)と\( B\)の大小関係でpow(\(A\),\(C\))とpow(\(B\),\(C\))の大小関係がわかります。ただし\(C\)の偶奇で判定方法が少し変わるので場合分けをして考えます。

\(C\)が奇数の場合

\(A\)と\(B\)の大小関係がそのままpow(\(A\),\(C\))とpow(\(B\),\(C\))の大小関係になる。

例えば
\(A=5,\, B=8, \, C=3\)のとき、つまり\(A \leq B\)のときは、pow(\(A\),\(C\))\(\, \leq \,\)pow(\(B\),\(C\))
\(A=-5,\, B=-1, \, C=3\)のとき、つまり\(A \leq B\)のときは、pow(\(A\),\(C\))\(\, \leq \,\)pow(\(B\),\(C\))
\(A=3,\, B=-2, \, C=3\)のとき、つまり\(A \geq B\)のときは、pow(\(A\),\(C\))\(\, \geq \,\)pow(\(B\),\(C\))

\(C\)が偶数の場合

整数を偶数回累乗すると必ず正の数になります。例えば\(-3^4 = 81\)。このことから\(A\)と\(B\)の絶対値の大小関係がpow(\(A\),\(C\))とpow(\(B\),\(C\))の大小関係になります。

例えば
\(A=5,\, B=8, \, C=3\)のとき、つまり\( |A| \leq |B|\)のときは、pow(\(A\),\(C\))\(\, \leq \,\)pow(\(B\),\(C\))
\(A=-5,\, B=-1, \, C=3\)のとき、つまり\(|A| \geq |B|\)のときは、pow(\(A\),\(C\))\(\, \geq \,\)pow(\(B\),\(C\))
\(A=3,\, B=-2, \, C=3\)のとき、つまり\( |A| \geq |B|\)のときは、pow(\(A\),\(C\))\(\, \geq \,\)pow(\(B\),\(C\))

ソースコード

#include <bits/stdc++.h>

int main() {
  int a, b, c; std::cin >> a >> b >> c;
  if (c%2 == 0) { // Cが偶数の場合はAとBの絶対値を比較すればよい
    a = std::abs(a);
    b = std::abs(b);
  }
  char ans = '=';
  if (a > b) ans = '>';
  else if (a < b) ans = '<';

  std::cout << ans << std::endl;
  return 0;
}

D – Kth Excluded

問題はこちら

解説

愚直にfor文などを書いてクエリを処理していると間に合わないので、工夫する必要があります。

公式の解説の解説と同じように1以上\(A_i\)未満の整数で\(A_1,A_2,\ldots,A_N\)のいずれとも異なる正の整数を良い整数と呼ぶことにします。\(s_i\)を\(A_i\)未満の良い整数の個数として記録しておきます。例えば\(A=(3,5,6,7)\)とすると\(s=(2,3,3,3)\)となります。そしてクエリ\(K_i\)に対しては\(s_i\)を二分探索し\(K_i \leq s_r\)となるインデックス\(\,r\)、または\(K_i > s_l\)となるインデックス\(\,l\)を見つけます。

言い換えると\(A_r\)未満に良い整数が\(K_i\)個以上あり、\(A_l\)未満に良い整数が\(K_i\)個未満あるような\(\,r\)と\(\,l\)を見つけます。(下図のようなイメージ)

後は今まで計算したものを使って\(K_i\)番目の整数を求めるだけです。ここからは0-indexedとして説明します。

\(l = -1\)の時(\(r = 0\))

\(s_0 \geq K_i\)となり\(A_0\)までに\(K_i番目の\)良い整数が存在するので、答えは\(K_i\)となります。


\(l \geq 0\)の時(上図のようなイメージ)

求める整数は\(A_l + (K_i – s_i)\)で計算できます。\(A_l\)から(\(K_i-s_i\))個先に答えがあるということです。

二分探索のわかりやすい解説はこちら

ソースコード

#include <bits/stdc++.h>

void binary_search(
    long long* arr, 
    const long long& key,
    const int& n,
    int& l,
    int& r) 
{
  l = -1;
  r = n;

  while (r - l > 1) {
    int m = (r - l) / 2 + l;
    if (arr[m] >= key) 
      r = m;
    else 
      l = m;
  }
}

int main() {
  int n, q; std::cin >> n >> q;
  long long* a = new long long[n];
  for (int i = 0; i < n; ++i) std::cin >> a[i];

  // s[i] := 1以上a[i]未満の数でA_0,A_1,...,A_N-1のいずれとも異なる数字の数
  long long* s = new long long[n];
  s[0] = a[0] - 1;
  for (int i = 1; i < n; ++i)
    s[i] = s[i-1] + (a[i] - a[i-1] - 1);

  for (int i = 0; i < q; ++i) {
    long long k; std::cin >> k;
    // l(left): s[i] < kとなる最大のindex
    // r(right): s[i] >= kとなる最小のindex
    int l, r; 
    binary_search(s, k, n, l, r);
    long long ans;
    if (l == -1) 
      ans = k;
    else
      ans = a[l] + (k - s[l]);
    std::cout << ans << std::endl;
  }

  delete[] s;
  delete[] a;
  return 0;
}

競技プログラミングの最新記事4件