이틀 전에 있었던 코드포스 라운드 689의 풀이이다. 개인적으로 적절한 그림 등과 함께 깔끔한 문제들이 나왔던 것 같다. 다만, B 문제의 제한을 좀 더 작게 줬으면 더 직관적이었을 것 같다.
단순히 길이가 \(N\)인 \(abcabc...\) 문자열을 출력해주면 된다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T; cin >> T;
while (T--) {
long long n, k; cin >> n >> k;
for (int i = 0; i < n; i++) {
if (i % 3 == 0)cout << "a";
if (i % 3 == 1)cout << "b";
if (i % 3 == 2)cout << "c";
}cout << '\n';
}
}
일단, 문제 자체는 이 문제와 동일하다. 그런데, 제한이 \(N \le 500\)으로 더 작다. 나는 일단 이 문제가 \(O(N^3)\)으로 안 풀린다고 생각해서 \(O(N^2logN)\)으로 어렵게 풀었다. 나중에 알아보니 보통 \(N \le 500\)정도일 때는 \(O(N^3)\)이 돌아간다고 한다. 출제자의 의도를 잘 파악해야겠다고 느꼈다.
내가 푼 방식은 먼저 각 행에 대해 Prefix Sum을 구해놓고, 하나의 열을 잡아 고정시킨 뒤 위에서부터 아래로 내려가며 Prefix Sum을 이용해 이분 탐색하는 방식이다. 이 과정에서 평소의 버릇대로 Prefix Sum을 1-based로 만들어놨는데, 이걸 실수로 0-based로 처리해서 디버깅하는데 약 20분이 걸렸다. 이런 실수를 좀 줄여야겠다.
어렵지 않게 구현할 수 있는 DP로도 이 문제를 풀 수 있다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T; cin >> T;
while (T--) {
int N, M; cin >> N >> M;
vector<string>v;
for (int i = 0; i < N; i++) {
string in; cin >> in;
v.push_back(in);
}
vector<vector<int>> psum;
for (int i = 0; i < N; i++) {
vector<int> cur(M + 1);
for (int j = 0; j < M; j++) {
cur[j + 1] = cur[j] + (v[i][j] == '*');
}
psum.push_back(cur);
}
long long ans = 0;
for (int j = 0; j < M; j++) {
int cur = -1;
for (int i = 0; i < N; i++) {
if (v[i][j] == '.') {
cur = -1;
continue;
}
int st = 0, en = cur + 1;
int mx = 0;
while (st <= en) {
int mid = (st + en) / 2;
if (mid + j + 1 > M) {
en = mid - 1;
continue;
}
if (j - mid < 0) {
en = mid - 1;
continue;
}
if (psum[i][j + mid + 1] - psum[i][j - mid] == mid * 2 + 1) {
st = mid + 1;
mx = mid;
}
else {
en = mid - 1;
}
}
cur = mx;
ans += mx + 1;
}
}
cout << ans << '\n';
}
}
흔하지 않은 유형인 확률을 이용하는 문제이다. 풀이는 간단한데, 정렬되어야 하는 가장 인덱스가 큰 원소를 구하고, 그 인덱스까지 영향을 주는 쿼리만 모아서 1에서 해당 확률을 빼준 뒤 전부 곱해준 뒤에, 1에서 그 값을 빼주면 답이다.
이 문제를 풀 때 주의해야 하는 점이 하나 있는데, 이미 정렬이 되어 있으면 답이 무조건 1인데, 그렇다고 1을 출력하고 바로 continue를 해버리면 인풋이 꼬여버린다는 점이다. 꼭 쿼리 인풋도 다 받도록 하자.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, double> pid;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T; cin >> T;
while (T--) {
int n, q, tl = -1; cin >> n >> q;
vector<int> perm(n); for (auto& i : perm) cin >> i;
vector<pid> query;
for (int i = n - 1, cnt = 0; i >= 0; i--, cnt++) {
if (perm[i] != n - cnt) {
tl = n - cnt; break;
}
}
for (int i = 0; i < q; i++) {
int rg; double pr; cin >> rg >> pr;
if (rg < tl) continue;
query.push_back({ rg, pr });
}
sort(query.begin(), query.end());
double res = 1;
for (int i = query.size() - 1; i >= 0; i--) {
res *= (1 - query[i].second);
}
if (tl == -1) {
cout << 1 << '\n'; continue;
}
cout << 1.0 - res << '\n';
}
}
문제가 요구하는 것은 굉장히 자명하다. 먼저, 문제대로 모든 Segment를 나누면 공간 복잡도가 \(O(NlogN)\)임을 캐치해야 한다. 그러면, 모든 Segment에 대해서 분할 정복으로 문제를 해결할 수 있음을 알 수 있다. 하나의 Segment에 대해 수행해야 할 연산은 아래와 같다.
1. Segment의 최댓값, 최솟값을 구해서 평균을 구한다.
2. 평균의 upper_bound를 구한다.
3. upper_bound를 기준으로 좌우로 Segment를 분리한다.
4. Segment를 얻을 때 마다 구간합을 구해 set에 넣는다.
5. 쿼리는 set을 이용하여 \(logN\)에 처리할 수 있다.
1번, 4번 연산을 위해 Segment Tree를 사용할 수도 있고, 업데이트가 없으므로 Sparse Table, Prefix Sum등 정말 다양한 풀이를 사용할 수 있다. 나는 구간합, 구간 최댓값, 구간 최솟값을 각각 구할 수 있는 Segment Tree 3개를 만들었다.
#include <bits/stdc++.h>
using namespace std;
const long long INF = 2100000000000000;
struct SegTree {
int sz, st, dep;
vector<long long> pw2, v;
SegTree(int size) {
long long k = 1;
for (int i = 0; i < 30; i++) pw2.push_back(k), k <<= 1;
sz = size; v.resize(sz * 4, 0); dep = 1;
while (1) {
if (sz <= pw2[dep - 1])break;
dep++;
}
st = pw2[dep - 1] - 1;
}
void init(long long val) {
for (int i = 1; i < 4 * sz; i++) v[i] = val;
}
long long val(int ind) {
ind++;
return v[st + ind];
}
void update(int ind, long long val) {
ind++;
v[st + ind] = val; ind = (ind + 1) / 2;
for (int i = dep - 1; i >= 1; i--) {
int cur = pw2[i - 1] - 1 + ind;
v[cur] = v[cur * 2] + v[cur * 2 + 1];
ind = (ind + 1) / 2;
}
}
long long query(int start, int end) {
start++; end++;
long long ret = 0;
start += st; end += st;
while (start <= end) {
if (start % 2 == 1)ret += v[start];
if (end % 2 == 0)ret += v[end];
start = (start + 1) / 2;
end = (end - 1) / 2;
}
return ret;
}
};
struct SegTree2 {
int sz, st, dep;
vector<long long> pw2, v;
SegTree2(int size) {
long long k = 1;
for (int i = 0; i < 30; i++) pw2.push_back(k), k <<= 1;
sz = size; v.resize(sz * 4, -INF); dep = 1;
while (1) {
if (sz <= pw2[dep - 1])break;
dep++;
}
st = pw2[dep - 1] - 1;
}
void init(long long val) {
for (int i = 1; i < 4 * sz; i++) v[i] = val;
}
long long val(int ind) {
ind++;
return v[st + ind];
}
void update(int ind, long long val) {
ind++;
v[st + ind] = val; ind = (ind + 1) / 2;
for (int i = dep - 1; i >= 1; i--) {
int cur = pw2[i - 1] - 1 + ind;
v[cur] = max(v[cur * 2], v[cur * 2 + 1]);
ind = (ind + 1) / 2;
}
}
long long query(int start, int end) {
start++; end++;
long long ret = 0;
start += st; end += st;
while (start <= end) {
if (start % 2 == 1)ret = max(ret, v[start]);
if (end % 2 == 0)ret = max(ret, v[end]);
start = (start + 1) / 2;
end = (end - 1) / 2;
}
return ret;
}
};
struct SegTree3 {
int sz, st, dep;
vector<long long> pw2, v;
SegTree3(int size) {
long long k = 1;
for (int i = 0; i < 30; i++) pw2.push_back(k), k <<= 1;
sz = size; v.resize(sz * 4, INF); dep = 1;
while (1) {
if (sz <= pw2[dep - 1])break;
dep++;
}
st = pw2[dep - 1] - 1;
}
void init(long long val) {
for (int i = 1; i < 4 * sz; i++) v[i] = val;
}
long long val(int ind) {
ind++;
return v[st + ind];
}
void update(int ind, long long val) {
ind++;
v[st + ind] = val; ind = (ind + 1) / 2;
for (int i = dep - 1; i >= 1; i--) {
int cur = pw2[i - 1] - 1 + ind;
v[cur] = min(v[cur * 2], v[cur * 2 + 1]);
ind = (ind + 1) / 2;
}
}
long long query(int start, int end) {
start++; end++;
long long ret = INF;
start += st; end += st;
while (start <= end) {
if (start % 2 == 1)ret = min(ret, v[start]);
if (end % 2 == 0)ret = min(ret, v[end]);
start = (start + 1) / 2;
end = (end - 1) / 2;
}
return ret;
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T; cin >> T;
while (T--) {
int N, Q; cin >> N >> Q;
SegTree *sg = new SegTree(N + 1);
SegTree2 *mxsg = new SegTree2(N + 1);
SegTree3 *mnsg = new SegTree3(N + 1);
vector<long long> v(N);
for (int i = 0; i < N; i++) {
cin >> v[i];
}
sort(v.begin(), v.end());
for (int i = 0; i < N; i++) {
sg->update(i, v[i]);
mxsg->update(i, v[i]);
mnsg->update(i, v[i]);
}
set<long long> s;
queue<pair<int, int>> q;
q.push({ 0,N - 1 });
while (!q.empty()) {
int lf, rg;
tie(lf, rg) = q.front(); q.pop();
if (lf > rg)continue;
s.insert(sg->query(lf, rg));
if (lf == rg)continue;
long long mn, mx;
mn = mnsg->query(lf, rg);
mx = mxsg->query(lf, rg);
long long mid = (mn + mx) / 2;
auto it = upper_bound(v.begin() + lf, v.begin() + rg + 1, mid) - v.begin();
if (it > rg)continue;
q.push({ lf,it-1 }); q.push({ it,rg });
}
while (Q--) {
long long in; cin >> in;
if (s.find(in) != s.end()) {
cout << "Yes\n";
}
else {
cout << "No\n";
}
}
}
}
'알고리즘' 카테고리의 다른 글
| Codeforces Global Round 12 (0) | 2020.12.07 |
|---|---|
| Codeforces Round #687 (Div.2) (0) | 2020.11.30 |
| Codeforces Round #686 (Div.3) (0) | 2020.11.25 |
| Codeforces Round #685 (Div.2) (0) | 2020.11.24 |
| Educational Codeforces Round 98 (Div.2) (0) | 2020.11.21 |
