AtCoder Beginner Contest 424 の A/B/C/D 問題の解法 #ABC424
2025-09-20AtCoder Beginner Contest 424 の A/B/C/D 問題の解法。
実装はこちら atcoder/abc/401-500/424 · michimani/atcoder 。
A - Isosceles
3つの整数 \(a\), \(b\), \(c\) が与えられたとき、どの2つかが等しいかどうかを判定する問題。
実装では、3つの数値のうち任意の2つが等しい場合（\(a = b\) または \(b = c\) または \(c = a\)）に “Yes” を出力し、すべてが異なる場合に “No” を出力する。
#include <iostream>
using namespace std;
using ui = unsigned int;
int main()
{
ui a, b, c;
cin >> a >> b >> c;
if (a == b || b == c || c == a)
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
B - Perfect
\(n\) 人のうち各人が \(m\) 回正解すると特定の処理を行う問題。\(k\) 回のクエリで人と得点が与えられ、\(m\) 回正解に達した人を順番に出力する。
実装では、各人の得点を配列 \(p\) で管理し、すでに出力した人を記録するマップ \(e\) を使用している。クエリごとに該当の人の得点を増やし、得点が \(m\) に達してまだ出力していない場合、その人の番号を結果文字列に追加する。
#include <iostream>
#include <vector>
#include <map>
using namespace std;
using ui = unsigned int;
int main()
{
ui n, m, k;
cin >> n >> m >> k;
vector<ui> p(n);
ui a = 0, b = 0;
string ans = "";
map<ui, bool> e = {};
for (; k--;)
{
cin >> a >> b;
p[a - 1]++;
if (p[a - 1] == m && !e[a])
{
ans += to_string(a) + " ";
e[a] = true;
}
}
if (ans.length() > 0)
ans.pop_back();
cout << ans << endl;
return 0;
}
C - New Skill Acquired
\(n\) 個のタスクがあり、各タスクは最大2つの依存関係を持つ。依存関係のないタスクから開始して、条件を満たしたタスクを順次実行していき、最終的に実行可能なタスクの総数を求める問題。
トポロジカルソートアルゴリズムの使用
実装では、トポロジカルソートの考え方を使用している。トポロジカルソートは有向非環グラフ（DAG）において、依存関係を満たしながらノードを線形に並べるアルゴリズム。
この問題でのトポロジカルソートの適用：
- 初期化: 依存関係のないタスク（両方の依存が0）をキューに追加
- BFS処理: キューからタスクを取り出し、そのタスクに依存する他のタスクをチェック
- 依存解決: タスクが実行可能になる条件は、2つの依存のうち少なくとも一方が満たされること
- 連鎖処理: 新たに実行可能になったタスクをキューに追加して処理を継続
通常のトポロジカルソートとの違いは、各タスクが2つの依存関係を持ち、OR条件（少なくとも一方が満たされればよい）で実行可能になる点。これにより、従来の入次数ベースのトポロジカルソートではなく、BFSベースの依存解決アプローチを採用している。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
int n;
cin >> n;
vector<pair<int, int>> s(n + 1);
vector<vector<int>> depends(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> s[i].first >> s[i].second;
if (s[i].first != 0)
depends[s[i].first].push_back(i);
if (s[i].second != 0)
depends[s[i].second].push_back(i);
}
vector<bool> l(n + 1, false);
queue<int> q;
for (int i = 1; i <= n; i++)
{
if (s[i].first == 0 && s[i].second == 0)
{
l[i] = true;
q.push(i);
}
}
while (!q.empty())
{
int current = q.front();
q.pop();
for (int dependent : depends[current])
{
if (!l[dependent])
{
if ((s[dependent].first == 0 || l[s[dependent].first]) || (s[dependent].second == 0 || l[s[dependent].second]))
{
l[dependent] = true;
q.push(dependent);
}
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
if (l[i])
ans++;
cout << ans << endl;
return 0;
}
D - 2x2 Erasing 2
\(h \times w\) のグリッドがあり、各セルは ‘#’ または ‘.’ で構成される。各行に対してマスクを設定し、2×2の正方形がすべて選択されないようにしながら、’#’ のセルを選択するのに必要な最小変更数を求める問題。
ビットマスクDPアルゴリズムの使用
実装ではビットマスク動的プログラミングを使用している。これは状態をビットで表現し、各ビットが特定の条件（この場合は各列の選択状態）を表すDP手法。
このアルゴリズムの適用方法：
- 状態定義:
dp[i][mask]= \(i\) 行目でマスクmaskを使った場合の最小変更数 - ビットマスク: 各行で \(w\) 個の列それぞれの選択状態を1ビットで表現（
1 << w通りの状態） - 状態遷移: 前の行のマスクと現在行のマスクの組み合わせをすべて試行
- 制約チェック: 2×2正方形の制約を満たすかを隣接する2列×2行で確認
bool tl = (prev_mask & (1 << j)) != 0; // 左上 bool tr = (prev_mask & (1 << (j + 1))) != 0; // 右上 bool bl = (cur_mask & (1 << j)) != 0; // 左下 bool br = (cur_mask & (1 << (j + 1))) != 0; // 右下 - コスト計算: ‘#‘セルが選択されていない場合にペナルティを加算
計算量: \(O(h \times 4^w \times w)\) となり、\(w\) が小さい場合に効率的。ビットマスクDPは状態数が指数的だが、制約が小さい問題で威力を発揮する典型的なアルゴリズム。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int h, w;
cin >> h >> w;
vector<string> g(h);
for (int i = 0; i < h; i++)
cin >> g[i];
vector<vector<int>> dp(h + 1, vector<int>(1 << w, 1e9));
dp[0][0] = 0;
for (int i = 0; i < h; i++)
{
for (int prev_mask = 0; prev_mask < (1 << w); prev_mask++)
{
if (dp[i][prev_mask] == 1e9)
continue;
for (int cur_mask = 0; cur_mask < (1 << w); cur_mask++)
{
int changes = 0;
bool valid = true;
for (int j = 0; j < w; j++)
{
if (g[i][j] == '#' && !(cur_mask & (1 << j)))
changes++;
}
if (i > 0)
{
for (int j = 0; j < w - 1; j++)
{
bool tl = (prev_mask & (1 << j)) != 0;
bool tr = (prev_mask & (1 << (j + 1))) != 0;
bool bl = (cur_mask & (1 << j)) != 0;
bool br = (cur_mask & (1 << (j + 1))) != 0;
if (tl && tr && bl && br)
{
valid = false;
break;
}
}
}
if (valid)
dp[i + 1][cur_mask] = min(dp[i + 1][cur_mask], dp[i][prev_mask] + changes);
}
}
}
int ans = 1e9;
for (int mask = 0; mask < (1 << w); mask++)
ans = min(ans, dp[h][mask]);
cout << ans << endl;
}
return 0;
}
comments powered by Disqus