AtCoder Beginner Contest 338 の A/B/C 問題の解法 #ABC338
2024-01-29AtCoder Beginner Contest 338 の A/B/C 問題の解法。
実装はこちら atcoder/abc/301-400/338 · michimani/atcoder
A - Capitalized?
S[0] が大文字で、 S[1] 以降が小文字であるかどうかを判定する。
大文字であることの判定は、 char 型の値に対しては、 'A' <= c && c <= 'Z' という条件式で判定できる。入力値はすべて英字であることから、 S[0] <= 'Z' 且つ S[i] > 'Z' (\(i = 1,2, \dots\)) であることを確認すればよい。逆にいいうと、それを満たさない時点で No と出力して終了すればよい。
#include <iostream>
using namespace std;
using ui = unsigned int;
int main()
{
string s;
cin >> s;
if (s[0] > 'Z')
{
cout << "No" << endl;
return 0;
}
for (ui i = 1; i < s.length(); i++)
{
if (s[i] <= 'Z')
{
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
return 0;
}
提出 #49692373 - AtCoder Beginner Contest 338
B - Frequency
\(S\) に出現する文字の出現回数を map<char, ui> で記録する。
記録した map を走査して、出現回数を key、同じ出現回数の文字の集合を value として map<ui, map<char, bool>> に記録し直す。
ここで value を map<char, bool> としているのは、 C++ の std:map では map の要素は key の昇順でソートされることを利用するためである。
記録し直したあとは、 その map の最後の要素 (=出現回数が一番多い文字群) の最初の要素 (=アルファベット順で最も早い文字) を出力すればよい。
#include <iostream>
#include <map>
using namespace std;
using ui = unsigned int;
int main()
{
string s;
cin >> s;
map<char, ui> cm;
for (auto c : s)
{
cm[c]++;
}
map<ui, map<char, bool>> ccm;
auto it = cm.begin();
while (it != cm.end())
{
ccm[it->second][it->first] = true;
it++;
}
cout << ccm.rbegin()->second.begin()->first << endl;
return 0;
}
提出 #49697596 - AtCoder Beginner Contest 338
C - Leftover Recipes
全体の方針として、料理 A を作る数を決めてその際に残った材料で料理 B が何人分作れるかを調べ、その合計値の最大値を答えとする。
まず、料理 A のみ、または料理 B のみを作った場合の最大値を求める。これは、 \(\min( \lfloor \frac{Q_i}{A_i} \rfloor)\) および \(\min( \lfloor \frac{Q_i}{B_i} \rfloor)\) \((1 \leq i \leq N)\)で求められる。
このとき、 \(A_i = 0\) および \(B_i = 0\) となる場合があることに注意する。
\(\min( \lfloor \frac{Q_i}{A_i} \rfloor)\) を料理 A を作ることができる最大値を \(a_{max}\) として、料理 A を \(a_{max}, a_{max}-1, \cdots, 1, 0\) 人分作ることを考える。それぞれの場合において残った材料で料理 B が何人分作れるかを調べ、その合計値を計算する。
最後に、それらの合計値の中から最大のものを出力する。
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
using ui = unsigned int;
int main()
{
ui n;
cin >> n;
vector<ui> q(n, 0);
for (auto &qq : q)
{
cin >> qq;
}
const ui mx = 10000000;
ui ac = mx;
vector<ui> a(n, 0);
for (ui i = 0; i < n; i++)
{
cin >> a[i];
if (a[i] > 0)
{
ac = min(ac, q[i] / a[i]);
}
}
ui bc = mx;
vector<ui> b(n, 0);
for (ui i = 0; i < n; i++)
{
cin >> b[i];
if (b[i] > 0)
{
bc = min(bc, q[i] / b[i]);
}
}
ui ans = 0;
for (ui acc = ac + 1; acc > 0; acc--)
{
ui bcc = bc;
for (ui i = 0; i < n; i++)
{
if (q[i] - (a[i] * (acc - 1)) < b[i])
{
bcc = 0;
break;
}
if (b[i] > 0)
{
bcc = min(bcc, (q[i] - (a[i] * (acc - 1))) / b[i]);
}
}
ans = max(ans, (acc - 1) + bcc);
}
cout << ans << endl;
return 0;
}
提出 #49744136 - AtCoder Beginner Contest 338
comments powered by Disqus