AtCoder Beginner Contest 094 の A/B/C 問題の解法 #ABC094
2024-02-27AtCoder Beginner Contest 094 の A/B/C 問題の解法。
実装はこちら atcoder/abc/001-100/094 · michimani/atcoder 。
A - Cats and Dogs
\(A\) 匹は猫であることがわかっているので \(X \geq A\) である必要がある。また、 \(A + B \lt X\) の場合は猫が余ることになるので、 \(A + B \geq X\) である必要がある。
以上より、 \(X \geq A\) かつ \(A + B \geq X\) である場合に YES を、それ以外の場合に NO を出力すればよい。
#include <iostream>
using namespace std;
using ui = unsigned int;
int main()
{
ui a, b, x;
cin >> a >> b >> x;
cout << (x >= a && x <= a + b ? "YES" : "NO") << endl;
return 0;
}
提出 #50671304 - AtCoder Beginner Contest 094
B - Toll Gates
各マスへの移動コストを \(0\) で初期化し、 \(i = 1,2, \dots, M\) のマスに対しては \(1\) で更新する。
左のマスから順に見ていき、 \(X\) 番目までとそれ以降とでそれぞれコストの合計値を計算し、小さい方を出力する。
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
using ui = unsigned int;
int main()
{
ui n, m, x;
cin >> n >> m >> x;
vector<ui> a(n, 0);
for (; m--;)
{
ui ai;
cin >> ai;
a[ai - 1] = 1;
}
ui f = 0, b = 0;
for (ui i = 0; i < n; i++)
{
if (i + 1 < x)
f += a[i];
else if (i + 1 > x)
b += a[i];
}
cout << min(f, b) << endl;
return 0;
}
提出 #50671175 - AtCoder Beginner Contest 094
C - Many Medians
各 \(X_i\) に対して、元々のインデックス \(i\) と値 \(X_i\) を pair<ui, ui> x で保持し、値の昇順でソートしておく。
元々のインデックスとソート後のインデックスとの対応を map<ui, ui> iti に記録する。
元々のインデックス \(i = 1,2, \dots, N\) に対して、 その値がソート後の数列の何番目かを iti[i] で取得し、その値と \(N/2\) (これは \(N-1\) 個の要素の中央値となるインデックス) との大小関係を調べる。
iti[i] が \(N/2\) 以下場合は、中央値より前の要素が削除されることになるので \(N/2 + 1\) を中央値となるインデックスとする。
iti[i] が \(N/2\) より大きい場合は、中央値より後ろの要素が削除されることになるので、中央値となるインデックスには影響なくそのまま \(N/2\) を中央値となるインデックスとする。
(問題文の \(1, 2, \dots, N\) はプログラム上では \(0, 1, \dots, N-1\) となることに注意)
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
using ui = unsigned int;
bool comp(pair<ui, ui> &l, pair<ui, ui> &r)
{
return l.second < r.second;
}
int main()
{
ui n;
cin >> n;
vector<pair<ui, ui>> x(n);
for (ui i = 0; i < n; i++)
{
ui xx;
cin >> xx;
x[i] = {i, xx};
}
sort(x.begin(), x.end(), comp);
map<ui, ui> iti; // org -> sorted;
for (ui i = 0; i < n; i++)
iti[x[i].first] = i;
ui mid = n / 2 - 1;
for (ui i = 0; i < n; i++)
{
if (iti[i] <= mid)
cout << x[mid + 1].second << endl;
else
cout << x[mid].second << endl;
}
return 0;
}
提出 #50671083 - AtCoder Beginner Contest 094
comments powered by Disqus