部分文字列と部分配列
目的は、文字列 a と b を部分配列として含む最短の文字列を見つけることです。その長さは a と b の長さの合計から、両方で共通する文字数を引いたものです。a は必ず含まれるため、b の各文字が a で順番に現れるかをチェックします。
注意: 部分文字列は連続した文字列ですが、部分配列は順序を保ちつつ連続性は必要ありません。
#include <bits/stdc++.h>
using namespace std;
void solve() {
string a, b;
cin >> a >> b;
int result = a.size() + b.size();
for (int start = 0; start < b.size(); ++start) {
int overlap = 0, index = start;
for (int i = 0; i < a.size() && index < b.size(); ++i) {
if (b[index] == a[i]) {
++overlap;
++index;
}
}
result = min(result, a.size() + b.size() - overlap);
}
cout << result << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int test_cases;
cin >> test_cases;
while (test_cases--) {
solve();
}
return 0;
}順列の出力
配列を奇数と偶数を交互に出力することで、分割されないようにします。奇数位置には昇順、偶数位置には降順で配置します。
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> sequence(n);
int even_index = 0, odd_index = 1;
for (int i = 1; i <= n; ++i) {
if (i % 2 == 1) {
sequence[even_index] = i;
even_index += 2;
} else {
sequence[odd_index] = i;
odd_index += 2;
}
}
for (int num : sequence) {
cout << num << " ";
}
cout << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int test_cases;
cin >> test_cases;
while (test_cases--) {
solve();
}
return 0;
}モンスターの攻撃!
モンスターの移動距離が同じものはグループ化し、それぞれのグループに対して順番に処理します。一度に処理できる数を超える場合は "NO" を出力します。
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, k;
cin >> n >> k;
vector<long long> strength(n), distance(n);
for (auto& s : strength) cin >> s;
for (auto& d : distance) cin >> d;
map<long long, long long> grouped_distances;
for (int i = 0; i < n; ++i) {
grouped_distances[abs(distance[i])] += strength[i];
}
long long remaining = k;
for (const auto& [dist, total_strength] : grouped_distances) {
if (total_strength > remaining) {
cout << "NO\n";
return;
}
remaining -= total_strength;
}
cout << "YES\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int test_cases;
cin >> test_cases;
while (test_cases--) {
solve();
}
return 0;
}非常に異なる配列
配列 a と b の長さが異なる場合でも、a の末尾と b の先頭をペアリングして最大の差分を求めます。b の残りの要素と a の先頭をペアリングして同様に計算し、最大値を選択します。
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (auto& x : a) cin >> x;
for (auto& x : b) cin >> x;
sort(a.begin(), a.end());
sort(b.begin(), b.end(), greater<>());
long long max_difference = 0;
for (int i = 0; i < n; ++i) {
max_difference = max(max_difference, accumulate(a.begin() + i, a.end(), 0LL) +
accumulate(b.begin(), b.begin() + n - i, 0LL, [](long long sum, int val) { return sum - val; }));
}
cout << max_difference << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int test_cases;
cin >> test_cases;
while (test_cases--) {
solve();
}
return 0;
}合計ゲーム
Alice は最大の数を選び、Bob は選んだ数を負の数にするという戦略を繰り返します。Bob のターンでは選んだ数の二倍を引くため、前処理で累積和を計算します。
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, k, x;
cin >> n >> k >> x;
vector<int> numbers(n);
for (auto& num : numbers) cin >> num;
sort(numbers.begin(), numbers.end(), greater<>());
long long total_sum = accumulate(numbers.begin(), numbers.end(), 0LL);
long long best_score = LONG_LONG_MIN;
long long current_sum = 0;
for (int i = 0; i < k; ++i) {
current_sum += numbers[i];
long long bob_turn = 2 * accumulate(numbers.begin() + i, numbers.begin() + min(n, i + x), 0LL);
best_score = max(best_score, total_sum - current_sum - bob_turn);
}
cout << best_score << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int test_cases;
cin >> test_cases;
while (test_cases--) {
solve();
}
return 0;
}最初の文字または2番目の文字を削除する
2番目の文字を削除してから最初の文字を削除する操作は、最初の文字を2回削除することと同じです。したがって、最初の k 個の文字について、それぞれのユニークな文字数をカウントします。
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
set<char> unique_chars;
int operations = 0;
for (char c : s) {
unique_chars.insert(c);
operations += unique_chars.size();
}
cout << operations << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int test_cases;
cin >> test_cases;
while (test_cases--) {
solve();
}
return 0;
}クエスト
a の前 n 個の合計と、b の最大値を組み合わせることで最大の結果を求めます。b の最大値を常に更新しながら、a の各要素について計算を行います。
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n), b(n);
for (auto& x : a) cin >> x;
for (auto& x : b) cin >> x;
long long best_result = 0, prefix_sum = 0, max_b = 0;
for (int i = 0; i < min(n, k); ++i) {
prefix_sum += a[i];
max_b = max(max_b, b[i]);
best_result = max(best_result, prefix_sum + max_b * (k - i - 1));
}
cout << best_result << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int test_cases;
cin >> test_cases;
while (test_cases--) {
solve();
}
return 0;
}交換と削除
文字列内の '0' と '1' の数を数え、それぞれの数がなくなるまで交互に削除します。最後に残った数が削除すべき数となります。
#include <bits/stdc++.h>
using namespace std;
void solve() {
string s;
cin >> s;
int count_zero = 0, count_one = 0;
for (char c : s) {
if (c == '0') ++count_zero;
else ++count_one;
}
for (char c : s) {
if (c == '0') {
if (count_one == 0) break;
--count_one;
} else {
if (count_zero == 0) break;
--count_zero;
}
}
cout << count_zero + count_one << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int test_cases;
cin >> test_cases;
while (test_cases--) {
solve();
}
return 0;
}もう一つ壊れたキーボード
'b' と 'B' に対応する文字をスタックに保存し、それぞれの文字が出現した順序を保持します。最後に、スタックから削除された文字を除いた残りの文字列を出力します。
#include <bits/stdc++.h>
using namespace std;
void solve() {
string s;
cin >> s;
stack<int> lower_b, upper_B;
bitset<1000005> marked;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == 'b') {
if (!lower_b.empty()) {
marked[lower_b.top()] = true;
lower_b.pop();
}
} else if (s[i] == 'B') {
if (!upper_B.empty()) {
marked[upper_B.top()] = true;
upper_B.pop();
}
} else if (islower(s[i])) {
lower_b.push(i);
} else if (isupper(s[i])) {
upper_B.push(i);
}
}
for (int i = 0; i < s.size(); ++i) {
if (!marked[i]) cout << s[i];
}
cout << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int test_cases;
cin >> test_cases;
while (test_cases--) {
solve();
}
return 0;
}