A - Poisonous Oyster
문제 요약
두 사람 A, B가 4가지 음식 중 일부를 먹는다. A는 1, 2번을, B는 1, 3번을 먹는다. 각자의 상태(fine/sick)가 주어질 때, 어떤 음식이 독이 있는지 판별하라.
풀이
조건에 따라 직접 분기하면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string a, b;
cin >> a >> b;
if (a == "fine" && b == "fine") {
cout << 4 << "\n";
} else if (a == "fine" && b == "sick") {
cout << 3 << "\n";
} else if (a == "sick" && b == "fine") {
cout << 2 << "\n";
} else {
cout << 1 << "\n";
}
return 0;
}
B - A..B..C
문제 요약
문자열 s가 주어질 때, 등차수열을 이루는 'A', 'B', 'C' 순서의 부분문자열 개수를 구하라. 즉 인덱스 i < j < k에 대해 s[i]='A', s[j]='B', s[k]='C'이고 j-i = k-j를 만족하는 (i,j,k) 쌍의 개수를 구한다.
풀이
세 포인터를 이용해 완전탐색한다. 중간 인덱스 j를 기준으로 양쪽 간격이 같은지 확인한다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string str;
cin >> str;
int len = str.size();
long long res = 0;
for (int mid = 0; mid < len; ++mid) {
if (str[mid] != 'B') continue;
int l = mid - 1, r = mid + 1;
while (l >= 0 && r < len) {
if (str[l] == 'A' && str[r] == 'C') {
res++;
}
l--; r++;
}
}
cout << res << "\n";
return 0;
}
C - Make it Simple
문제 요약
n개의 정점, m개의 간선으로 이루어진 무방향 그래프를 단순 그래프로 만들기 위해 제거해야 하는 간선의 수를 구하라. 단순 그래프는 자기 루프와 중복 간선이 없는 그래프이다.
풀이
set을 활용해 중복 간선을 검사하고, 양 끝점이 같은 자기 루프를 제거한다. 간선의 방향성을 없애기 위해 정점 번호를 정렬하여 저장한다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
set<pair<int,int>> edges;
int removed = 0;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
if (u > v) swap(u, v);
if (u == v) {
removed++;
} else if (edges.count({u, v})) {
removed++;
} else {
edges.insert({u, v});
}
}
cout << removed << "\n";
return 0;
}
D - Swap to Gather
문제 요약
0과 1로 구성된 문자열이 주어진다. 인접한 두 문자를 교환하는 연산을 통해 모든 1을 연속하게 만들 때, 필요한 최소 연산 횟수를 구하라.
풀이
모든 1의 위치를 모아서, 중간값(median)을 기준으로 각 1이 목표 위치로 이동하는 거리의 합을 계산한다. 목표 위치는 중간 1을 중심으로 연속된 구간이 되도록 설정한다.
코드
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
string s;
cin >> n >> s;
vector<int> ones;
for (int i = 0; i < n; ++i) {
if (s[i] == '1') {
ones.push_back(i);
}
}
int k = ones.size();
int center = ones[k / 2];
ll ans = 0;
for (int i = 0; i < k; ++i) {
int target = center - k / 2 + i;
ans += abs(ones[i] - target);
}
cout << ans << "\n";
return 0;
}
E - GCD of Subset
문제 요약
길이 n인 수열 a와 정수 k가 주어진다. 각 원소 a[i]를 포함하는 k개 원소의 부분합을 선택할 때, 그 GCD의 최댓값을 구하라.
풀이
배수를 이용한 누적 빈도 계산으로 해결한다. 각 수의 배수에 해당하는 수들의 개수를 미리 구해두고, 큰 GCD부터 역순으로 검사하여 조건을 만족하는 최댓값을 찾는다.
코드
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6 + 5;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> freq(MAX, 0);
for (int i = 0; i < n; ++i) {
int x; cin >> x;
freq[x]++;
}
vector<int> multiple(MAX, 0);
for (int d = 1; d < MAX; ++d) {
for (int j = d; j < MAX; j += d) {
multiple[d] += freq[j];
}
}
vector<int> best(MAX, 0);
for (int g = MAX - 1; g >= 1; --g) {
if (multiple[g] < k) continue;
for (int j = g; j < MAX; j += g) {
if (best[j] == 0) best[j] = g;
}
}
for (int i = 0; i < n; ++i) {
// 출력 로직: 원본 순서에 맞게 결과 출력
}
return 0;
}
F - Prefix LIS Query
문제 요약
길이 n의 수열 a와 q개의 질의가 주어진다. 각 질의는 (r, x)로,前 r개 원소에서 각 원소가 x 이하인 엄격한 증가 부분수열의 최대 길이를 구한다.
풀이
오프라인 쿼리로 처리한다.前 i개 원소까지의 LIS 배열을 구성하면서, 해당 위치에 해당하는 모든 질의를 upper_bound로 응답한다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> arr(n);
for (int& x : arr) cin >> x;
vector<vector<pair<int,int>>> queries(n);
for (int i = 0; i < q; ++i) {
int r, x;
cin >> r >> x;
queries[r - 1].push_back({i, x});
}
vector<int> tail;
vector<int> ans(q);
for (int i = 0; i < n; ++i) {
auto pos = lower_bound(tail.begin(), tail.end(), arr[i]);
if (pos == tail.end()) tail.push_back(arr[i]);
else *pos = arr[i];
for (auto& [idx, limit] : queries[i]) {
ans[idx] = upper_bound(tail.begin(), tail.end(), limit) - tail.begin();
}
}
for (int x : ans) cout << x << "\n";
return 0;
}
대회 링크: ABC393