AtCoder Beginner Contest 415 の A/B/C 問題の解法 #ABC415
2025-07-19AtCoder Beginner Contest 415 の A/B/C 問題の解法。
実装はこちら atcoder/abc/401-500/415 · michimani/atcoder 。
A - Unsupported Type
長さ \(N\) の整数列 \(A\) に整数 \(X\) が含まれているかを判定する。
set を使って重複を排除した数列を作成し、 set::contains メソッドで \(X\) が含まれているかを確認する。含まれていれば "Yes"、含まれていなければ "No" を出力する。
#include <iostream>
#include <set>
using namespace std;
using ui = unsigned int;
int main()
{
ui n;
cin >> n;
set<ui> a;
for (; n--;)
{
ui aa;
cin >> aa;
a.insert(aa);
}
ui x;
cin >> x;
cout << (a.contains(x) ? "Yes" : "No") << endl;
return 0;
}
B - Pick Two
倉庫ロボットが、最も番号の小さいセクションから順番に2つのパッケージを取り出していく問題。
文字列 \(S\) を左から順に走査し、 '#' を見つけるたびにそのセクション番号（1-indexed）を出力する。最初の '#' では番号のみを出力し、2つ目の '#' では ,番号 を出力して改行する。
#include <iostream>
using namespace std;
using ui = unsigned int;
int main()
{
string s;
cin >> s;
ui c = 0;
for (ui i = 0; i < s.length(); i++)
{
if (s[i] == '#')
{
if (c == 1)
{
cout << ',';
cout << (i + 1) << endl;
c = 0;
}
else
{
cout << (i + 1);
c++;
}
}
}
return 0;
}
C - Mixture
\(N\) 種類の化学物質を危険な状態を作らずに混合できるかを判定する問題。
ビット列で化学物質の混合状態を表現し、BFS（幅優先探索）を使って安全に全ての化学物質を混合できるかを調べる。状態 \(0\)（何も混合していない状態）から開始し、各段階で新しい化学物質を1つずつ追加していく。文字列 \(S\) で危険な状態が '1' で示されているので、次の状態が '0'（安全）の場合のみ進める。
最終的に状態 \((1 « N) - 1\)（全ての化学物質が混合された状態）に到達できれば "Yes"、到達できなければ "No" を出力する。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using ui = unsigned int;
bool can_mix_all(ui n, string s)
{
vector<bool> visited(1 << n, false);
queue<int> q;
q.push(0);
visited[0] = true;
while (!q.empty())
{
int current = q.front();
q.pop();
if (current == (1 << n) - 1)
return true;
for (ui i = 0; i < n; i++)
{
if (!(current & (1 << i)))
{
int next = current | (1 << i);
if (!visited[next] && s[next - 1] == '0')
{
visited[next] = true;
q.push(next);
}
}
}
}
return false;
}
int main()
{
ui t;
cin >> t;
for (; t--;)
{
ui n;
string s;
cin >> n >> s;
cout << (can_mix_all(n, s) ? "Yes" : "No") << endl;
}
return 0;
}
comments powered by Disqus