AtCoder Beginner Contest 413 の A/B/C 問題の解法 #ABC413
2025-07-05AtCoder Beginner Contest 413 の A/B/C 問題の解法。
実装はこちら atcoder/abc/401-500/413 · michimani/atcoder 。
A - Content Too Large
N個のアイテムのサイズの合計が、サイズMのバッグに収まるかを判定する問題。
アイテムのサイズを順番に読み込み、累計和を計算する。累計和がMを超えた時点で "No"
を出力し、全てのアイテムを読み込んでも累計和がMを超えなければ "Yes"
を出力する。
#include <iostream>
using namespace std;
using ui = unsigned int;
int main()
{
ui n, m;
cin >> n >> m;
ui sum = 0;
for (; n--;)
{
ui a;
cin >> a;
sum += a;
if (sum > m)
{
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
return 0;
}
B - cat 2
N個の文字列から異なる2つを選んで連結した時に作れる異なる文字列の個数を求める問題。
すべての文字列のペア(異なるインデックス i, j)について、文字列 s[i] + s[j]
を作成し、unordered_set
を使って重複を排除する。最終的に set のサイズが答えとなる。
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
using ui = unsigned int;
int main()
{
ui n;
cin >> n;
vector<string> s(n);
for (auto &ss : s)
cin >> ss;
unordered_set<string> p = {};
for (ui i = 0; i < n; i++)
{
for (ui j = 0; j < n; j++)
{
if (i == j)
continue;
p.insert(s[i] + s[j]);
}
}
cout << p.size() << endl;
return 0;
}
C - Large Queue
キューに対して要素の追加と先頭からの取り出し操作を効率的に処理する問題。
deque
を使ってキューを実装する。各要素は {価値, 個数}
のペアで管理する。操作1では要素を末尾に追加し、操作2では先頭から指定個数だけ取り出しながら価値の合計を計算する。取り出し時は、先頭要素の個数が足りない場合は要素を削除し、次の要素から継続して取り出す。
#include <iostream>
#include <deque>
#include <cmath>
using namespace std;
using ui = unsigned int;
using ull = unsigned long long;
using ll = long long;
int main()
{
ui q;
cin >> q;
deque<pair<ull, ull>> A;
ui a;
ull b, c;
for (; q--;)
{
cin >> a;
if (a == 1)
{
cin >> b >> c;
A.push_back({c, b});
}
else
{
// a == 2
cin >> b;
ull sum = 0;
ull remaining = b;
while (remaining > 0 && !A.empty())
{
ull take = min(remaining, A.front().second);
sum += take * A.front().first;
remaining -= take;
A.front().second -= take;
if (A.front().second == 0)
A.pop_front();
}
cout << sum << endl;
}
}
return 0;
}
comments powered by Disqus