第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313） #ABC313
2023-12-28第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313） の A/B/C の解法。
実装はこちら atcoder/abc/301-400/313 · michimani/atcoder 。
A - To Be Saikyo
\(P_1\) と \(\max \lbrace P_2, P_3, \dots , P_N \rbrace\) の差と、 \(0\) の大きい方を出力する。
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int n;
cin >> n;
int n1;
cin >> n1;
int nx = 0;
for (int i = 0; i < n - 1; i++)
{
int p;
cin >> p;
nx = max(nx, p);
}
cout << max(0, nx + 1 - n1) << endl;
return 0;
}
提出 #48896302 - 第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313）
B - Who is Saikyo?
強い/弱い が確定した人をそれぞれ map<int, bool> で保持するようにして、 \(A_i\) を強い方 (w) に、 \(B_i\) を弱い方 (l) に追加していく。このとき、 \(B_i\) が w に含まれていれば w から削除する。最後に w のサイズが \(1\) であればその人が最強、それ以外の場合は最強の人を確定できないので -1 を出力する。
#include <iostream>
#include <map>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
map<int, bool> w;
map<int, bool> l;
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
if (l.count(a) == 0)
{
w[a] = true;
}
if (w.count(b) > 0)
{
w.erase(b);
}
l[b] = true;
}
if (w.size() != 1)
{
cout << -1 << endl;
}
else
{
cout << w.begin()->first << endl;
}
return 0;
}
提出 #48896264 - 第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313）
C - Approximate Equalization 2
C - Approximate Equalization 2
※公式の解説を参考にした
C - Approximate Equalization 2 解説 by yuto1115 - 第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313）
元の数列に対して操作したあとの数列をあらかじめ決めて、その数列の各値との差の絶対値を計算するという方針。
今回の問題であれば、 操作前後で数列の各値の総和が変化しない という性質をもとに、操作後の数列を決めることができる。
操作後の数列 \(B\) について、最大値と最小値の差分は \(1\) 以下であることから、総和を \(N\) で割った余りを \(1\) ずつ分配するという点も重要。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ui = unsigned int;
using ll = long long;
int main()
{
ui n;
cin >> n;
if (n == 1)
{
cout << 0 << endl;
return 0;
}
vector<ll> a(n, 0);
ll sum = 0;
for (auto &aa : a)
{
cin >> aa;
sum += aa;
}
vector<ll> b(n, sum / n);
for (ui i = 0; i < sum % n; i++)
{
b[n - 1 - i]++;
}
sort(a.begin(), a.end());
ll cnt = 0;
for (ui i = 0; i < n; i++)
{
cnt += abs(a[i] - b[i]);
}
cout << cnt / 2 << endl;
return 0;
}
提出 #48896079 - 第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313）
comments powered by Disqus