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;
}