AtCoder Beginner Contest 416 の A/B/C/D 問題の解法 #ABC416
2025-07-26AtCoder Beginner Contest 416 の A/B/C/D 問題の解法。
実装はこちら atcoder/abc/401-500/416 · michimani/atcoder 。
A - Vacation Validation
文字列 \(S\) の \(l\) 番目から \(r\) 番目までの文字がすべて 'o' であるかを確認する。
配列のインデックスは0から始まるので、 \(i\) を \(l-1\) から \(r-1\) まで回して、 \(S[i]\) が 'o' でない場合は "No" を出力する。すべて 'o' であれば "Yes" を出力する。
#include <iostream>
using namespace std;
using ui = unsigned int;
using ull = unsigned long long;
using ll = long long;
int main()
{
ui n, l, r;
cin >> n >> l >> r;
string s;
cin >> s;
for (ui i = l - 1; i < r; i++)
{
if (s[i] != 'o')
{
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
return 0;
}
B - 1D Akari
各位置について、現在までの最後に配置された 'o' の位置を記録し、その位置から現在の位置まで間に '#' があるかを確認する。
'#' でない位置を順番に確認し、直前の 'o' との間に '#' がある場合にのみ 'o' を配置し、それ以外は '.' を配置する。
#include <iostream>
using namespace std;
using ui = unsigned int;
int main()
{
string s;
cin >> s;
string t = s;
int last_o = -2;
for (ui i = 0; i < s.length(); i++)
{
if (s[i] == '#')
continue;
bool can_place = true;
if (last_o >= 0)
{
bool has_hash = false;
for (int j = last_o + 1; j < (int)i; j++)
{
if (s[j] == '#')
{
has_hash = true;
break;
}
}
if (!has_hash)
can_place = false;
}
if (can_place)
{
t[i] = 'o';
last_o = i;
}
else
{
t[i] = '.';
}
}
cout << t << endl;
return 0;
}
C - Concat (X-th)
\(n\) 個の文字列から \(k\) 個を選んで重複を許して並べ、全ての組み合わせを辞書順に並べたときの \(x\) 番目の文字列を求める。
再帰関数 generate を使って、すべての可能な長さ \(k\) の列を生成する。各位置で \(n\) 個の文字列すべてを試し、結果を vector<string> results に保存する。
最後に results を辞書順にソートし、 \(x-1\) 番目（0-indexedなので）の要素を出力する。
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
using ui = unsigned int;
int main()
{
ui n, k, x;
cin >> n >> k >> x;
vector<string> s(n);
for (ui i = 0; i < n; i++)
{
cin >> s[i];
}
vector<string> results;
function<void(vector<int> &, int)> generate = [&](vector<int> &seq, ui pos)
{
if (pos == k)
{
string result = "";
for (ui i = 0; i < k; i++)
{
result += s[seq[i]];
}
results.push_back(result);
return;
}
for (ui i = 0; i < n; i++)
{
seq[pos] = i;
generate(seq, pos + 1);
}
};
vector<int> seq(k);
generate(seq, 0);
sort(results.begin(), results.end());
cout << results[x - 1] << endl;
return 0;
}
D - Match, Mod, Minimize 2
各テストケースごとに、配列 \(a\) と \(b\) をソートし、各 \(b_i\) に対して最適な \(a_j\) を選ぶ。
\((b_i + a_j) \bmod m\) を最小化したいので、 \(a_j \geq m - b_i\) となる最小の \(a_j\) を見つける。それと、最小の \(a\) 要素との結果を比較し、より小さい値を選ぶ。
multiset を使用して利用可能な \(a\) の値を管理し、選ばれた値は削除する。
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
using ui = unsigned int;
using ll = long long;
int main()
{
ui t;
cin >> t;
for (; t--;)
{
ui n;
ll m;
cin >> n >> m;
vector<ll> a(n), b(n);
for (ui i = 0; i < n; i++)
cin >> a[i];
for (ui i = 0; i < n; i++)
cin >> b[i];
sort(a.begin(), a.end());
sort(b.begin(), b.end());
ll total = 0;
multiset<ll> available(a.begin(), a.end());
for (ui i = 0; i < n; i++)
{
ll bi = b[i];
ll target = m - bi;
auto it = available.lower_bound(target);
ll best_val = (bi + *available.begin()) % m;
auto best_it = available.begin();
if (it != available.end())
{
ll val = (bi + *it) % m;
if (val < best_val)
{
best_val = val;
best_it = it;
}
}
if (it != available.begin())
{
--it;
ll val = (bi + *it) % m;
if (val < best_val)
{
best_val = val;
best_it = it;
}
}
total += best_val;
available.erase(best_it);
}
cout << total << endl;
}
return 0;
}
comments powered by Disqus