AtCoder Beginner Contest 206（Sponsored by Panasonic） #ABC206
2024-01-05AtCoder Beginner Contest 206（Sponsored by Panasonic） の A/B/C 問題の解法。
実装はこちら atcoder/abc/201-300/206 · michimani/atcoder 。
A - Maxi-Buying
\(N\) を unsigned int として受け取り、 \(1.08\) 倍ではなく \(108\) 倍する。その後 \(100\) で割ることで、 \(1.08\) 倍して小数点以下を切り捨てた状態と同じになる。あとはこの値と \(206\) を比較して結果を出力する。
#include <iostream>
using namespace std;
using ui = unsigned int;
int main()
{
ui n;
cin >> n;
n *= 108;
const ui t = 206;
if (n / 100 < t)
{
cout << "Yay!" << endl;
}
else if (n / 100 == t)
{
cout << "so-so" << endl;
}
else
{
cout << ":(" << endl;
}
return 0;
}
提出 #49025550 - AtCoder Beginner Contest 206（Sponsored by Panasonic）
B - Savings
\(i\) 日目の合計貯金額を \(S_i\) とすると、 \(S_1 = 1, S_i = S_{i-1} + i (i \geq 2)\) となる。問題の条件であれば \(i\) を順に足していって \(S_i\) が初めて \(N\) を超えるときの \(i\) を求めればよい。
#include <iostream>
using namespace std;
using ui = unsigned int;
ui add(ui &t, ui d, ui sum)
{
if (sum >= t)
{
return d - 1;
}
return add(t, d + 1, sum + d);
}
int main()
{
ui n;
cin >> n;
cout << add(n, 0, 0) << endl;
return 0;
}
提出 #49025699 - AtCoder Beginner Contest 206（Sponsored by Panasonic）
C - Swappable
\( 1\leq i \lt j \leq N\) を満たす \((i,j)\) の組み合わせは、 \(1 ,\dots, N\) から 2 つの数を選ぶ組み合わせと同じ数だけ存在する。この組み合わせの数は \({}_N C_2 = \frac{N(N-1)}{2}\) である。
\({}_N C_2\) は \(A_i \neq A_j \) を満たさないものも含まれているので、 \(A_i = A_j\) を満たすものをここから除外する。 \(A_i = A_j\) を満たすものは、 \(A_i\) が同じ数となる個数を \(k\) とすると、\({}_k C_2\) である。
どの数が複数個現れるかは \(A_i\) を受け付けるときに map<unsigned int, unsigned int> m で記録していく。
入力をすべて受け付けたあと、 m の各要素に対して \(value\) が \(2\) 以上のものに対して \({}_{value} C_2\) を計算して、 \({}_N C_2\) から引いていく。残った値が答えとなる。
#include <iostream>
#include <map>
using namespace std;
using ull = unsigned long long;
ull nc2(ull n)
{
return (n * (n - 1)) / 2;
}
int main()
{
ull n = 0;
cin >> n;
map<ull, ull> m;
for (ull i = 0; i < n; i++)
{
ull a;
cin >> a;
if (m.count(a) == 0)
{
m[a] = 1;
}
else
{
m[a]++;
}
}
ull ans = nc2(n);
auto it = m.begin();
while (it != m.end())
{
if (it->second > 1)
{
ans -= nc2(it->second);
}
it++;
}
cout << ans << endl;
return 0;
}
提出 #49035808 - AtCoder Beginner Contest 206（Sponsored by Panasonic）
comments powered by Disqus